Home Page for CMSC 651 (Advanced Algorithms) Fall 1999

This is the web page for the class when it was taught in Fall 1999. I will have the TA make a new (and better) web page for the class in Spring 2002..

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

Office Hours: Thu 11-12. If you cannot make these hours, please make an appointment to see me at a different time.

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. These are in postscript.

Class Time: TuTh 11:00--12:15. CLB 0109.

MIDTERM WILL BE ON MONDAY IN CLASS, OCTOBER 25th. CLOSED BOOKS, CLOSED 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:

• Christos Papadimitriou and Ken Steiglitz, Combinatorial Optimization: Algorithms and Complexity.
• Robert Tarjan, Data Structures and Network Algorithms, SIAM, 1983.
• Cormen, Leiserson, Rivest, Introduction to Algorithms, MIT Press and McGraw Hill (1990).

Suggested Syllabus:

• Advanced Data Structures: F-heaps, Disjoint-sets etc.
• Analysis of Algorithms: Spanning Trees, Flows, Matchings etc.
• NP-completeness: Cook's theorem, reductions etc.
• Approximation Algorithms: Network Design, Graph Theory, Scheduling etc.

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

• Homework 1 Due 9/22/99 Solution 1.
• Homework 2 Due 10/06/99 Solution 2.
• Homework 3 Due 10/20/99 Solution 3.
• Homework 4 Due 11/10/99 Solution 4.
• Homework 5 Due 11/24/99 Solution 5.
• Homework 6 Due 12/13/99 Solution 6.

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.