Lectures for CMSC 651.
There is a postscript file accessible from my web page. Most topics are covered in those notes. Print the appropriate pages.
Lecture 1: Overview of Course
Lecture 2: Cancelled due to campus closure (snow)
Lecture 3:
Introduction to Amortized Analysis.
Lecture 4:
Binomial Heaps Fibonacci Heaps
Lecture 5:
Disjoint Set Data Structure
Lecture 6: Matroids and Greedy Algorithms
Lecture 7:
Min weight Branchings
Lecture 8: Popular Matchings
Lecture 9:
Matching Algorithm and Two Processor Scheduling
Lecture 10:
Weighted Matching
Lecture 11: Popular matchings
Lecture 12:
Flows (Ford Fulkerson, Edmonds-Karp)
Lecture 13:
Flows (Preflow-Push -- see Cormen book )
Lecture 14: Applications of Flows: Baseball elimination, Densest Subgraphs (Kleinberg-Tardos CH 7)
Lecture 15: Applications of Flows: Open Pit mining, Circulations with lower bounds, Application to a vision problem (Kleinberg-Tardos CH 7)
Lecture 16: MIDTERM (Mar 16)
Lecture 17: Disuss exams and Min cost Flows
Lecture 18:
Min cost flows
Lecture 19:
Linear Programming and Duality
Lecture 20:
More on LP Duality
Lecture 21: Linear Programming
Lecture 22:
The Primal-Dual Method
and
Weighted Vertex Cover
Lecture 23:
The Primal-Dual Method applied to Matching
Lecture 24:
NP-completeness (Cook's Theorem)
Lecture 25:
NP-completeness (Reductions)
Lecture 26: NP-completeness (Reductions) and Generalized Assignment Problem
Lecture 27: Color Coding
Lecture 28: Matroid Intersection
Lecture 29: REVIEW (May 11)