- 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.
CMSC 651: Advanced Algorithms
Spring 2002
You may review your final exam in the Instructor's office on Wed, May 29th between 10 and 12 am.
Final exam is on May 21st. 1.30 - 3.30 pm in JMP 3201.You are allowed THREE handwritten sheets of paper (8.5 by 11 inches). The sheets could be written both sides. That is the only material allowed. The sheets HAVE to be handwritten.
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. This is to make sure that Google does not grab our homework solutions!
Graded homework 5 is available. You can collect yours at the TA office hours this Friday. Homework 6 will be available on Monday during the TA office hours.
General Information 
Course
Overview Homeworks
and Handouts Lectures Related
Stuff
General Information
| Class Time | Tue, Thur 9:30-10:45. |
| Room | CLB 0109 |
| Instructor | Samir Khuller |
| Office | A.V. Williams 3217. |
| Office phone | 405 6765 |
| Office Hours | Tue 10.45-11.45 and by appointment. |
| samir@cs.umd.edu |
| Teaching Assistant | Srinivasan Parthasarathy |
| Office | A.V. Williams 4140. |
| Office Hours | Mon & Fri 2.30 - 3.30 |
| sri@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 through SIAM. While the books do overlap a little in their coverage of their material, their focus is slightly different.)Course Work and Grading
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.Homeworks 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 01
Homework 02
Homework 03
Homework 04
Homework 05
Homework 06
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.Lecture 01: Overview and Mortized Analysis
Lecture 02: Bipartite Matching
Lecture 03: Bipartite Matching
Lecture 04: Two Processor Scheduling
Lecture 05 : Chapter 10, Combinatorial Optimization, Papadimitriou & Steiglitz
Lecture 06: Faster Bipartite Matching
Lecture 07: Weighted Matching
Lecture 08: Flows
Lecture 09: Flows
Lecture 10 : Max flow algorithm, Chapter 9, Combinatorial Optimization, P & S
Lecture 11 : (Flow in Unary Capacity Networks) Chapter 9, Combinatorial Optimization, P & S
Lecture 12 Introduction to Min Cost Flows
Lecture 13 : Min-mean cycle (Handout from Network Flow Book)
Lecture 14 : Min-mean cycle (Dynamic Programming)
Lecture 15 : Exam
Lecture 16 : Go over exam and finish min-mean cycle proof
Lecture 17 : Min Cost Flows - Shortest Paths (2 handouts)
Lecture 18 : Applications of Min Cost Flows - solving LP's (handout from Network Flow Book)
Lectures 19 & 20: Linear Programming and Duality
Lectures 21 & 22: Primal Dual Algorithms (read Chapter 5 of PS)
Lectures 23: Shortest Paths solved by a Primal Dual Algorithm (Chap 5)
Lecture 24: Min Cost Branchings
Lecture 25: Introduction to NP-completeness, 3 SAT to Graph coloring
Lecture 26: Reductions: 3SAT to Clique, 3 SAT to Vertex Cover, Clique to MultiProcessor Scheduling
Lecture 27: Cook's Theorem
Lecture 28: Approximation Algorithms: Vertex Cover