CMSC651 Analysis of Algorithms, Fall 2012
Schedule: Please click here for the
Major topics to be covered in class:
The class will have a strong overlap with Chandra Chekuri's
course. There will be no required textbook; the
following notes, slides, and videos available online, are useful
- 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,
principle for randomized algorithms, the rank bound in communication
- 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
- 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:
- Jeff Erickson's notes, homeworks, and exams from previous semesters
- Jeff Erickson: CS 573 (Fall 2010)
- Sariel Har-Peled: CS 573 (Fall 2009)
- Manuel Blum's lecture notes from Spring 2007
- Samir Khuller's lecture notes
- Chandra Chekuri: CS 473 (Fall 2010)
- Algorithms textbook by Dasgupta, Papadimitriou and Vazirani, and
- Algorithm Design by Kleinberg and Tardos; Kevin
Wayne's lecture slides based on the book available here.
Our additional goal is to foster independent group-based learning.
Students will do independent reading of
portions of a forthcoming
book by Hopcroft
and solve selected problems based on the book,
throughout the course. (Of course, Aravind will be happy to discuss any
questions about the book's material in his office hours.)
- Sundar Vishwanathan's lectures from 2008 on
reductions, NP, and NP-completeness:
video3. (Very good background if you have not yet seen NP-completeness.)
- Noga Alon on color coding, 2011.
- Erik Demaine and Charles Leiserson's lectures,
- Claire Mathieu's lectures, Spring 2012.
- Tim Roughgarden's lectures, Winter 2011.