Quick Links:
[Discussion & OH] [Schedule] [Calendar] [Problem Sets] [Policies] [Resources] [Staff]
| Date | Class # | Lecture | Module | Reading | Problem Set |
|---|---|---|---|---|---|
| Jan 25 | 1 | Introduction and Overview | Review 1 | 1, 2.1 - 2.2, 3.1 | PS1 out |
| Jan 27 | 2 | Stable Matching Problem | Review 2 | 1, 2.3 - 2.5 | |
| Feb 1 | 3 | Review on Graphs | Review 3 | 3.2 - 3.6 | PS1 in / PS2 out |
| Feb 3 | 4 | Interval Scheduling Problem | Greedy 1 | 4.1 | |
| Feb 8 | 5 | Scheduling Problem Variants | Greedy 2 | 4.2 | PS2 in / PS3 out |
| Feb 10 | 6 | Shortest Path Problem | Greedy 3 | 4.4 | |
| Feb 15 | 7 | Minimum Spanning Tree | Greedy 4 | 4.5 - 4.6 | |
| Feb 17 | 8 | Weighted Interval Scheduling Problem | Dynamic Programming 1 | 6.1 - 6.2 | |
| Feb 22 | 9 | Subset Sums and Knapsacks Problem | Dynamic Programming 2 | 6.4 | PS3 in / PS4 out |
| Feb 24 | 10 | Shortest Path with Negative Edges | Dynamic Programming 3 | 6.8, 6.10 | |
| Mar 1 | 11 | Mergesort Algorithm | Divide and Conquer 1 | 5.1 - 5.2 | |
| Mar 3 | 12 | Integer Multiplication Problem | Divide and Conquer 2 | 5.5 | |
| Mar 8 | 13 | Median Finding and Quicksort | Divide and Conquer 3 | 13.5 | PS4 in |
| Mar 10 | 14 | Midterm 1 | |||
| Mar 15 | 15 | Max Flow Problem | Network Flow 1 | 7.1 | PS5 out |
| Mar 17 | 16 | Max Flow and Min Cuts | Network Flow 2 | 7.2 - 7.3 | |
| Spring Break | |||||
| Mar 29 | 17 | Max Flow for Bipartite Matching | Network Flow 3 | 7.5, 7.7 | |
| Mar 31 | 18 | Polynomial-Time Reductions | Complexity 1 | 8.1 | |
| Apr 5 | 19 | Satisfiability Problem | Complexity 2 | 8.2 | PS6 out |
| Apr 7 | 20 | NP and NP-Complete Problems | Complexity 3 | 8.3 - 8.4 | PS5 in |
| Apr 12 | 21 | Traveling Salesman and Hamiltonian Cycle | Complexity 4 | 8.5 | |
| Apr 14 | 22 | PSPACE Problems | Complexity 5 | 9.1 - 9.3 | |
| Apr 19 | 23 | Load Balancing Problem | Approximation 1 | 11.1 | PS6 in /PS7 out (4/18) |
| Apr 21 | 24 | Set Cover and Vertex Cover Problems | Approximation 2 | 11.3 - 11.4 | |
| Apr 26 | 25 | PTAS for Knapsack Problem | Approximation 3 | 11.8 | PS7 in |
| Apr 28 | 26 | Midterm 2 |