Schedule: Please click here for the lecture-schedule.

Major topics to be covered in class:

• Basic complexity classes and NP-completeness; worst-case vs. average-case analyses, and self-improving algorithms (quick review).
• Recursion, Divide-and-conquer, Dynamic programming, Greedy algorithms and matroids.
• Lower bounds: the adversarial and information-theoretic methods, the minimax principle for randomized algorithms, the rank bound in communication complexity.
• Randomized algorithms: hashing and color-coding, concentration bounds, data streams and communication complexity, basic distributed algorithms.
• Three pillars of combinatorial optimization: shortest paths, network flow, matching.
• Linear programming and the polyhedral approach to combinatorial optimization.
• Approaches to intractability: heuristics, approximation algorithms (especially via rounding approaches), fixed-parameter tractability.
• The statement of the PCP Theorem and brief, high-level outline of Irit Dinur's proof; applications to inapproximability.
• The Unique-Games Conjecture (brief coverage).
• A brief study of multi-core processors and MapReduce.

Lecture notes and slides:

1. Jeff Erickson's notes, homeworks, and exams from previous semesters
2. Jeff Erickson: CS 573 (Fall 2010)
3. Sariel Har-Peled: CS 573 (Fall 2009)
4. Manuel Blum's lecture notes from Spring 2007
5. Samir Khuller's lecture notes
6. Chandra Chekuri: CS 473 (Fall 2010)
7. Algorithms textbook by Dasgupta, Papadimitriou and Vazirani, and errata
8. Algorithm Design by Kleinberg and Tardos; Kevin Wayne's lecture slides based on the book available here.

Videos:

1. Sundar Vishwanathan's lectures from 2008 on reductions, NP, and NP-completeness: video1, video2, and video3. (Very good background if you have not yet seen NP-completeness.)
2. Noga Alon on color coding, 2011.
3. Erik Demaine and Charles Leiserson's lectures, Fall 2005.
4. Claire Mathieu's lectures, Spring 2012.
5. Tim Roughgarden's lectures, Winter 2011.

Web Accessibility