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

- 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 25% for the homeworks, 35% for the midterm and
40% for the final exam.

- Homework 1
**POSTED**Due Feb 2 Solution 1 (POSTED). - Homework 2
**POSTED**Due Feb 16 Solution 2 (POSTED). - Homework 3
**POSTED**Due Feb 28 Solution 3 (POSTED). - Homework 4
**POSTED**Due Mar 14 Solution 4 (POSTED). - Homework 5
**POSTED**Due Apr 4 Solution 5 (POSTED). - Homework 6
**(POSTED)**Due Apr 13 Solution 6 (POSTED) . - Homework 7
**(POSTED)**Due Apr 27 Solution 7. - Homework 8
**(POSTED)**Due May 9 Solution 8**(POSTED).**

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