CMSC651 Analysis of Algorithms, Fall 2013
Schedule (dynamically updated; make sure to reload): Please click here for
the lecture-by-lecture schedule.
Major topics planned for class/HW (a few of these could eventually not be
covered in sufficient detail due to the university's snow-related closing
on 12/10):
- 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: alteration and random permutations, hashing and
color-coding, concentration bounds,
data streams and communication complexity,
distributed algorithms.
- Three pillars of combinatorial optimization: shortest paths, network flow, matching; study of matching in its different guises.
- 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.
- A brief study of multi-core processors and MapReduce.
There will be no required textbook; the
following notes, slides, and videos available online, are useful
resources.
Lecture notes, slides, and syllabi:
- 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 573 (Fall 2011)
- Algorithms textbook by Dasgupta, Papadimitriou and Vazirani, and
errata
- Algorithm Design by Kleinberg and Tardos; Kevin
Wayne's lecture slides based on the book available here.
Videos:
- 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.)
- Noga Alon on color coding, 2011.
- Erik Demaine and Charles Leiserson's lectures,
Fall 2005.
- Claire Mathieu's lectures, Spring 2012.
- Tim Roughgarden's lectures, Winter 2011.
Our additional goal is to foster independent group-based learning.
Students will do independent reading of
portions of
Welzl's notes and of the
Arora-Hazan-Kale survey. (Of course, Aravind will be happy to discuss any
questions about this material in his office hours.)
Web Accessibility