Algorithms Reading Group
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.
We meet weekly on Tuesdays, from 5 p.m. - 6 p.m. in Lindley Hall, room 101. Spring break week we will not be meeting. 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.
If you'd like to be added to the mailing list for the group, drop me a line: email@example.com.
This is our schedule of speakers for Spring 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, click it to send me an e-mail with details. Thanks!
|Jan. 12||Singular Value Decomposition||Prof. Paul Purdom|
|Jan. 19||Defining BPP and PCP Complexity Classes, pt. 1||Christopher Cole|
|Jan. 26||Defining BPP and PCP Complexity Classes, pt. 2||Christopher Cole|
|Feb. 2||Basic Computational Geometry||
|Feb. 9||Bayesian Filtering||Jeff Johnson|
|Feb. 16||Complexity of Finding Nash Equilibria||Christopher Cole|
|Feb. 23||Higher Order Complexity||Ramyaa Ramyaa|
|Mar. 2||Particle Filtering||Jeff Johnson|
|Mar. 9||Probabilistic Roadmap Motion Planning||Prof. Kris Hauser|
|Mar. 23||Minimizing Communication in Linear Algebra||Nilesh Narayanrao Mahajan|
|Mar. 30||Satisfiability||Prof. Paul Purdom|
|Apr. 6||Introduction to Factoring of Integers||Prof. Paul Purdom|
|Apr. 13||Generic Programming||Prof. Andrew Lumsdaine|
|Apr. 20||Algorithms in SAT/SMT Solvers||Nilesh Narayanrao Mahajan|
|Apr. 27||Factoring of Integers||Paul Grubbs|
|May. 4||On expressiveness and in-expressiveness result for query languages||Prof. Van Gucht|
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
- 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.
- 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.
- Complexity Zoo
- Beer & Algorithms
- 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)
Questions for the Group
- Can you construct a language that can only be solved by an algorithm running in time Θ(n100)? One of the arguments for polynomial time being tractable is that "often when an algorithm is found for a problem where the polynomial has high degree, a refinement is found that significantly reduces the degree." So is this a conjecture on a property of P, or is just that practical problems tend to have low degree?
The Time Hierarchy Theorem for deterministic TMs tells us, basically, that a TM that runs for a longer time can decide more languages than one that is restricted to run in a shorter time. Using this, I can say that some language exists that runs in time T(n) such that n99+ε < T(n) < n100, ε > 0. (And, technically, ε must be chosen so that n99+ε is "time-computable.") So, this question is really getting at constructing a reasonably natural language that takes Θ(n100) time to decide on a TM rather than just asserting it must exist. This is also in contrast to finding an algorithm that has Θ(n100) runtime, which is pretty easy for any decidable language.