January 21 Course Introductions, Greedy Algorithms I - KT 4.1
January 23 Greedy Algorithms II: Minimum Spanning Trees - KT 4.5, DPV 5.1
January 28 Dynamic Programming I: Intro (HW 1 Due) - KT 6.1, 6.6
January 30 Dynamic Programming II: Strings - KT 6.6, 6.5, DPV 6.3
February 4 Dynamic Programming III: Four Russians and Knapsack (HW 2 Due) - KT 6.4, DPV 6.4
February 6 Dynamic Programming IV: Further Applications - KT 6.3
February 11 Divide and Conquer I: Sorting and Multiplication (HW 3 Due) - KT 5.1-5.2, 5.5, DPV 2.1-2.3
February 13 Divide and Conquer II: Multiplication and Spatial Problems - KT 5.4, DPV 2.5
February 18 Divide and Conquer III: The Sorting Lower Bound and Median Finding (HW 4 Due) - DPV 2.4
February 20 Amortization I: Accounting
February 25 Amortization II: Potential Method - KT 4.6
February 27 Shortest Paths I: Graph Traversal and Topological Sort (Exam 1 Due - Unit I)
March 3 Shortest Paths II: Single-Source Shortest Path (HW 5 Due) - KT 4.4, DPV 4.4-4.5
March 5 Shortest Paths III: Single-Source and All-Pairs Shortest Path - 6.9-6.11, DPV 4.6-4.7
March 10 Network Flow I: Maximum Flows and Minimum Cuts (HW 6 Due) - KT 7.1-7.2, DPV 7.2
March 12 Network Flow II: Reductions - KT 7.5-7.6, DPV 7.2
March 14-29 Spring Break
March 31 Network Flow III: Edmonds-Karp and Image Segmentation - KT 7.3, 7.10
April 2 Stable Matching and Algorithmic Bias - KT 1.1
April 7 NP-Completeness I: Introduction to NP (HW 7 Due) - KT 8.1-8.4 (parts), DPV 8 (parts)
April 9 NP-Completeness II: A Collection of Reductions - KT 8.1 (parts), 8.8, DPV 8 (parts)
April 14 NP-Completeness III: Hamiltonian Cycle and Traveling Salesperson Problems (HW 8 Due) - KT 8.5, DPV 8 (parts)
April 16 NP-Completeness IV: Set Cover and Graph Coloring - KT 8.1 (parts), 8.7, DPV 8 (parts)
April 21 Modern Algorithms I: Approximation Algorithms (HW 9 Due)
April 23 Modern Algorithms II: Approximation Algorithms
April 28 Modern Algorithms III: Online Algorithms (HW 10 Due)
April 30 Modern Algorithms IV: Randomized Algorithms
May 11 & 14 Final Exam (all three units) - Final Project Due