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