CMSC 651: Advanced Algorithms
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
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
and Handouts Lectures Related
||Mon, Wed 3:30-4:45.
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.
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.
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.)
- Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein.
- Combinatorial Optimization by Papadimitriou and Steiglitz.
- Combinatorial Optimization by Cook, Cunningham, Pulleyblank and Schrijver.
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.42
Median : 82
90-100 : 7
80-89 : 15
70-79 : 10
60-69 : 1
<=59 : 2
Sample 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 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
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.
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