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.