Old Lectures for CMSC 651 (from 1998). These change each time I teach the course

• Lecture 1: Overview of Course
• Lectures 2 and 3: Kruskal's MST Algorithm and Disjoint Sets Data Structure
• Lecture 4: Boruvka's Algorithm and Yao's Algorithm for MST
• Lecture 5: Finish Yao's algorithm and start Amoritized Analysis
• Lecture 6: Binomial Heaps and Fibonacci Heaps
• Lecture 7: Fibonacci Heaps
• Lecture 8: Binomial heap creation and Dynamic Tables (Chap 18) + Matchings
• Lecture 9: Faster Matching Algorithm and Two Processor Scheduling
• Lecture 10: Weighted Matching
• Lecture 11: Weighted Matching (photocopied notes distributed)
• Lecture 12:Stable Marriage Problem and discussed Sample Midterm
• Lecture 13: Flows
• Midterm, OCT 25th.
• Lecture 14: No notes -- Read Tarjan's book for Blocking Flow methods.
• Lecture 15: No notes -- Read Handout (Papadimitriou and Steiglitz).
• Lecture 16: No notes -- Applications of Flows.
• Lecture 17: Preflow-Push Flow Method - read CLR.
• Lecture 18: Min cost flows
• Lecture 19: Min cost flows
• Lecture 20:Min cost flows:Applications (photocopy from book)
• Lecture 21: Linear Programming
• Lectures 22 and 23:The Primal-Dual Method (handwritten notes)
• Lecture 24: NP-completeness (Chap 36)
• Lecture 25: NP-completeness (Reductions)
• Lecture 26: Cook's Theorem
• Lecture 27: Summary of Course (Intro to approximations)