- Understanding techniques to design and analyse data structures. These will find applications in combinatorial algorithms that we study.
- Learning and designing efficient algorithms for basic graph theoretic problems that are used as building blocks elsewhere. These include shortest paths, minimum spanning trees, matching, flow etc.
- An understanding of the inherent complexity of problems: Polynomial time, NP-completeness, Approximation Algorithms etc.
- Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein.
- Combinatorial Optimization by Papadimitriou and Steiglitz.
- Combinatorial Optimization by Cook, Cunningham, Pulleyblank and Schrijver.
CMSC 651: Advanced Algorithms
Fall 2003
Solutions to a homework could be obtained by augmenting the class page URL
with the string sx.ps where x is replaced by the corresponding homework
number.
Homework 8 has been graded. You could either pick it up during the TA's office hours on Tuesday or from his office
AVW-4122 (if he is there).
Solutions 1-8 are now on the class page
Class on Dec 10th will start at 4pm. Prof. Boneh from Stanford is giving a talk 3-4 pm in AVW 2460.
Final exam: Dec 17 1:30-3:30, CSI 2117. Grades are now ready and have been entered into www.ares.umd.edu. If you cannot access them online come by to my office to check your grade.
General Information 
Course
Overview Homeworks
and Handouts Lectures Related
Stuff
General Information
Class Handout.| Class Time | Mon, Wed 3:30-4:45. |
| Room | CSIC 3120 |
| Instructor | Samir Khuller |
| Office | A.V. Williams 3369. |
| Office phone | 405 6765 |
| Office Hours | Mon, Tue 2-3 |
| samir@cs.umd.edu |
| Teaching Assistant | Chiu-Yuen Koo |
| Office | A.V. Williams 1151. |
| Office Hours | Tu 11-1 |
| cykoo@cs.umd.edu |
Course Overview
Techniques for the design and analysis of algorithms and data structures. Study of efficient algorithms from areas such as graph theory, networks, scheduling etc. Understanding of the inherent complexity of problems: polynomial time, NP-completeness and approximation algorithms.The following broad aims will be attempted.
Texts
We will cover material from three books. All three will be on reserve in the CS library. (Most of you should have the first one already, the second one is very cheap, and the third could be purchased. While the books do overlap a little in their coverage of their material, their focus is slightly different.)Course Work and Grading
These are subject to change and will depend on whether or not we have a TA. Course work will consist of homeworks, a midterm and a final exam. The relative weights of these will be 20% for the homeworks, 35% for the midterm and 45% for the final exam. Midterm will be on Oct 29th (CSIC 2117). The midterm will be CLOSED NOTES, CLOSED BOOK. Final is scheduled on Dec 17 (according to the fall 2003 list of classes).Statistics for the midterm
Average : 80.42Median : 82
90-100 : 7
80-89 : 15
70-79 : 10
60-69 : 1
<=59 : 2
Sample Exam
SAMPLE MIDTERM Sample Final Exam SAMPLE FINALHomeworks and Handouts
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. Homeworks will be due at the start of class on the due date. Late homeworks will not be accepted.Homework 0 (Ungraded HW)
Homework 1 (Due Sep 24) (Average: 85.39)
Homework 2 (Due Oct 1) (Average: 80.48)
Homework 3 (Due Oct 15) (Average: 84.70)
Homework 4 (Due Oct 22) (Average: 80.96) NOTE: lcm is lowest common multiple (problem 5). Common Error: You will lose 7 points for problem 3 if you don't specify the source vertex for the Bellman-Ford Algorithm. Note that you cannot pick an arbitrary vertex v as the source since the negative cycle may not be reachable from v.
Homework 5 (Due Nov 10 (changed)) (Average: 88.45)
Homework 6 (Due Nov 19 (Average: 83.25)
Homework 7 (Due Dec 3 (Average: 87.73)
Homework 8 (Due Dec 10 (Average: 88.91) CHANGED PROBLEM 4! Sorry for the confusion. If you printed a copy before 10:30am on Fr, please print it again.
Lecture Notes
Notes will be put online only after the lecture. From my web page you can get the entire set of lecture notes. Please print the relevant pages only. The notes contain lots of topics that we will not have time to cover in one semester! Or access the old class page CMSC 651 (Spring 2002).Lecture 01: Overview and Mortized Analysis
Lecture 02: Binomial and Fibonacci heaps
Lecture 03: Fibonacci Heaps and Two Processor Scheduling
Lecture 04: How to do Research (Gasarch CSIC 1121)
Lecture 05: Bipartite Matching
Lecture 06: Matching in general graphs (See Books)
Lecture 07: Weighted Matching
Lecture 08: Flows
Lecture 09: Flows
Lecture 10 : Max flow algorithm, Chapter 9, Combinatorial Optimization, P & S
Lecture 11 : Preflow-Push method (read CLR)
Lecture 12: Introduction to Min Cost Flows
Lecture 13: Min-Mean Cycle Algorithm
Lecture 14 : Min-mean cycle (Dynamic Programming-- See Handout)
Lecture 15 : Min Cost Flows - Shortest Paths. See Handout for applications of Min Cost Flows.
Lecture 16 : Review
Lecture 17 : MIDTERM (CSIC 2117, Oct 29)
Lecture 18: Exam Review
Lecture 19: Guest Lecture by Micah Adler (U Mass). In 2460 AVW 3-4pm. Randomized Algorithms for Network Security and Peer-to-Peer Systems
Lectures 20 and 21: Linear Programming
Lecture 22: Primal-Dual algorithms for LP's
Lecture 23: Weighted Matching solved by a Primal Dual Algorithm
Lectures 24 and 25: Introduction to NP-completeness, 3 SAT to Graph coloring, 3SAT to Clique, Clique to MultiProcessor Scheduling, 3 SAT to Disjoint Paths.
Lecture 26: 3 SAT to PARTITION.
Lecture 27: 2 SAT and Vertex Cover
Lecture 28: Cook's Theorem