Instructor: Samir Khuller Office: AVW 3369. Office phone: (301) 405--6765. E-mail: samir@cs.umd.edu.
Office Hours: TuTh 11-12 If you cannot make these hours, please make an appointment to see me at a different time.
Ghodsi's Office Hours: Tu 12:30--2:30, Thu 12:30--1:30 in AVW 1112.
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: Tu and Th 9:30--10:45am. CSI 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.
Course Work: Course work will consist of homeworks, and two exams on Oct 16 and Dec 6. All exams will be in class. Both exams will count as the MS Comp exam.
Do not forget to do the course evaluation!!!
Grading: The relative weights of these will be 20% for the homeworks, 40% for each exam.
Homeworks: