Home Page for CMSC 858Y (Topics in Algorithms: Combinatorial Optimization: Algorithms and Complexity)

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

Office Hours: Mon 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: Mon and Wed 3:30--4:45pm. CSIC 3120.

Course Overview: The main paradigm in the course will be the design and analysis of algorithms for combinatorial optimization. We will cover problems that can be solved optimally in polynomial time (matchings, flows, min-cost flows) as well as study problems that are NP-hard, and for which we can develop approximation algorithms. I expect that the students are already familiar with the material from CMSC 451 (minimum spanning trees, shortest paths, dynamic programming, NP-completeness etc.). I will spend the first few weeks covering some topics such as flows and matchings that you may or may not be familiar with from an undergraduate algorithms course.

Goals:

Texts:

Approximation Compendium .

Course Work: Course work will consist of a few ungraded homeworks (answers will be discussed in class), and two in class exams. The combined grade from both exams will count as the MS Comp exam.

Exam 2 will be from 3:30--5:00 in class on Mon, May 3

Do not forget to do the course evaluation!!!

Grading: The relative weights of these will be 50% for each exam.

Class Handout

Homeworks:

LIST OF LECTURES