CMSC 651: Advanced Algorithms
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
and Handouts Lectures Related
||Tue, Thur 9:30-10:45.
||A.V. Williams 3217.
||Tue 10.45-11.45 and by appointment.
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 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.
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
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