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):

There will be no required textbook; the following notes, slides, and videos available online, are useful resources.

Lecture notes, slides, and syllabi:

  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 573 (Fall 2011)
  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.


  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.
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.)