Home Page for CMSC 651 (Advanced Algorithms) Spring 2011

Instructor: Samir Khuller Office: AVW 3369. Office phone: (301) 405--6765. E-mail: samir@cs.umd.edu.

Office Hours: Mon Wed 11 - 12.

TA: Saeed Alaei Office: AVW 3457. Email: saeed@cs.umd.edu

Office Hours: Tue 1:30--3:00 and Fri 2:00--3:30

I will update this page every week during the semester. I will place all homeworks as well as solutions to homeworks here. If you have any trouble accessing them, please let me know.

Class Time: Mon Wed 3:30--4:45. CSIC 3118.

MIDTERM WILL BE on March 16 (Wed) -- CLOSED BOOKS, CLOSED NOTES.

FINAL EXAM WILL BE OPEN NOTES.

Course Overview: The main paradigm in the course will be the design and analysis of algorithms for discrete optimization problems. A majority of the problems considered will be graph theoretic. I expect that the students are already familiar with the material from CMSC 451 (minimum spanning trees, shortest paths, dynamic programming, NP-completeness etc.).

Texts (all have some useful materials and you will need to refer to them from time to time). The subject is such that you learn by solving problems and by writing proofs. These texts all do something really well, I have not yet found the one book that does everything the way I want it covered.

Suggested Syllabus:

Course Work: Course work will consist of homeworks, a midterm and a final exam.
Grading: The relative weights of these will be 25% for the homeworks, 35% for the midterm and 40% for the final exam.

Class Handout
Approximation Compendium .

Lecture Notes
Notes will be put online only after the lecture. From my web page you can get the entire set of lecture notes from when I taught the course in 1996.