Algorithms Reading Group
Main Menu
About
We'll be focusing on topics in algorithm theory with special emphasis given towards the end of the sessions to currently active areas of algorithms research.
Except for the first meeting, which will be on a Wednesday because of a scheduling conflict, we meet every other week on Mondays, from 4 p.m. - 5 p.m. in Lindley Hall, room 101. See the calendar for details on each meeting (topic, presenter, etc.). The meetings are open to all, please feel free to drop by any time. We usually have cookies and tea.
If you'd like to be added to the mailing list for the group, drop me a line: jj56@indiana.edu.
Credit
If you'd like to receive an independent study credit for group participation, there are the following requirements:
- You must attend each meeting.
- You must give at least one presentation.
- Your presentation must include some kind of supplementary material for the audience (like a reference, summary, etc.)
- Be prepared for Q&A.
If this is something you'd be interested in, let me know so we can get you set up: jj56@indiana.edu
Schedule
This is our schedule of speakers for Fall 2010 (although it is, like all things in life, subject to change). We still have openings, so if you'd like to speak on a given date, send me an e-mail: jj56@indiana.edu
| Date | Topic | Topic Resources | Presenter |
|---|---|---|---|
| Aug. 31 | Preliminary Meeting: Discussion of topics and presenters | N/A | N/A |
| Sept. 8 | Probabilistic Reasoning | Jeff Johnson | |
| Sept. 20 | Control Flow Analysis | Michael Adams | |
| Oct. 4 | Roundtable | Jeff Johnson | |
| Oct. 18 | Power and Limitations of Models of Data and Computation | Prof. Van Gucht | |
| Nov. 1 (1/2) | Image Segmentation | Weiran Li | |
| Nov. 1 (2/2) | Optical Recognition of Music Symbols | Rong Jin | |
| Nov. 15 | Fast Multiresolution Image Querying | Bingjing Zhang | |
| Nov. 30 | Reconstructing the World from Social Photo-sharing Websites | Prof. David Crandall |
Members
In no particular order, these are the current members of the group:
- Christine Task
- Christopher Cole
- Minh Tang
- Jeff Johnson
- Nilesh Narayanrao Mahajan
- Ramyaa Ramyaa
- Emel Gencer
- Girish Subramanian
- ChinHua Kong
- Brent Castle
- Torsten Hoefler
- Adrija Sen
- Prashnat R. Singhal
- Jong Choi
- Ben Kovitz
- Damien Sullivan
- Ammar Halabi
- Rebecca Ingram
- Mike Hansen
- Michael Adams
Resources
Courses
- B502 Computational Complexity (3 cr.) P: B501. Study of computational complexity classes, their intrinsic properties, and relations between them. Topics include time and space computational complexity. Reducibility and completeness of problems within complexity classes. Complexity of optimization problems. Complexity hierarchies. Relativization of the P =? NP conjecture. Parallel computation models and the class NC.
- B503 Algorithms Design and Analysis (3 cr.) P: Mathematics M216 and C343. Models, algorithms, recurrences, summations, growth rates. Probabilistic tools, upper and lower bounds; worst-case and average-case analysis, amortized analysis, dynamization. Comparison-based algorithms: search, selection, sorting, hashing. Information extraction algorithms (graphs, databases). Graphs algorithms: spanning trees, shortest paths, connectivity, depth-first search, breadth-first search. Credit not given for both B503 and B403.
- B510 Introduction to Applied Logic (3 cr.) Structures: relations between structures, term structures. Description: notation and meaning, substitution operations, first order formulas, database languages, program verification conditions, semantics valuation, normal forms, quantifier reduction, axiomatic theories. Proof: resolution, sequential calculi, natural deduction, automated theorem proving, semantic completeness. Limits of formalization: compactness, undecidability of truth, undecidability of canonical theories, non-formalizability of database theory.
Faculty
- Paul W. Purdom: Analysis of algorithms, rewriting systems, compilers, game playing, and singular value decomposition.
- David S. Wise: Current research interests pursue a paradigm for for solving matrix problems, specifically with a block-recursive perspective on arrays.
Sites
- http://rjlipton.wordpress.com/
- http://blog.computationalcomplexity.org/
- Complexity Zoo
- Beer & Algorithms
Literature
- Probabilistic Robotics
- Introduction to Algorithms
- The Analysis of Algorithms
- Computational Complexity: A Modern Approach
- Computational Geometry Introduction
- Computational Geometry Lecture Notes
- Randomized Algorithms (Amazon | Google Books): This book is available online at no cost through the IU Library.
- Introduction to Algorithms (CLRS) (Amazon | Google books)