CMSC651 Analysis of Algorithms, Fall 2012

Schedule: Please click here for the lecture-schedule.

Major topics to be covered in class:

The class will have a strong overlap with Chandra Chekuri's Fall 2011 course. There will be no required textbook; the following notes, slides, and videos available online, are useful resources.

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.
Our additional goal is to foster independent group-based learning. Students will do independent reading of portions of a forthcoming book by Hopcroft and Kannan, 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.)