Homework assignments are due at noon on the day indicated. Reading assignments are listed on the day they are assigned, and generally prepare you for the next class. Optional reading assignments are in brackets.
Note that this schedule is an aspirational approximation of what we'll do; it may be updated as the term goes on.
| Week 1: Intro; Stable Matching | ||||
| Date | Due | Class Topic | Out | Reading |
|---|---|---|---|---|
| 1. M 9/15 | Welcome; Course overview; Notation review; Intro to stable matching | PS0; PS1 | Preface, §1.1, §2.1–2 | |
| 2. W 9/17 | PS1 | Solving stable matching: brute force and the Gale–Shapley proposal algorithm | PS2 | §2.3–5 |
| 3. F 9/19 | PS0; PS1 | Gale–Shapley | §3.1 | |
| Week 2: Aymptotics, Proofs of Correctness, and Graphs | ||||
| 4. M 9/22 | PS2 | Stable-matching variants that better model the NRMP; Proofs and problem-solving | Posted asymptotics notes; §1.2; §3.2–3 | |
| 5. W 9/24 | PS2 | More proofs; Data structures; Asymptotics (O, Ω, Θ) | PS3 | §3.4–6 |
| 6. F 9/26 | PS2 | Graphs and some sample problems; Graph implementation | Q1 | §4.4 |
| Week 3: Greedy Algorithms | ||||
| 7. M 9/29 | Q1 | Graph traversal (BFS and DFS); Shortest paths in weighted graphs | §4.1 | |
| 8. W 10/1 | PS3 | Dijkstra's algorithm | PS4 | §4.2 |
| 9. F 10/3 | PS3 | Dijkstra's redux; Problem writeup critique | Q2 | §4.5–6 |
| Week 4: More Greedy Algorithms | ||||
| Date | Due | Class Topic | Out | Reading |
| 10. M 10/6 | Q2 | Greedy algorithms; Interval scheduling; Deadline Scheduling & exchange arguments | ||
| 11. W 10/8 | PS4 | Minimum Spanning Trees; MST algorithms: Reverse-Delete, Kruskal's, Prim's, and Borůvka's | PS5; Q3 | Jeff Erickson's notes on Disjoint Sets data structures |
| 12. F 10/10 | PS4 | Implementing Kruskal's and Borůvka's; The Union-Find / Disjoint Sets data structure | Optional: David Karger, Philip Klein, and Robert Tarjan. A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees. JACM, 1995. | |
| Week 5: Dynamic Programming Basics | ||||
| 13. M 10/13 | Q3 | Exam 1 | §6.1–3 | |
| 14. W 10/15 | PS5 | Intro to Dynamic Programming: Weighted Interval Scheduling, Recurrence Relations, and Memoization | PS6 | |
| 15. F 10/17 | PS5 | Sequence Alignment; Mid-Term evals | ||
| Week 6: Dynamic Programming | ||||
| XX. M 10/20 | No class (like a Marxist utopia) | |||
| 16. W 10/22 | PS6 | Sequence Alignment; Seam Carving | PS7 | §6.6 |
| 17. F 10/24 | PS6 | Seam Carving; Shortest Paths with negative weights: Bellman–Ford | §6.8 | |
| Week 7: DP Finale; Divide-and-Conquer | ||||
| Date | Due | Class Topic | Out | Reading |
| 18. M 10/27 | DP shortest paths: Floyd–Warshall; Divide-and-Conquer: Return of the Recurrence Relations! | |||
| 19. W 10/29 | PS7 | Counting Inversions | PS8 | |
| 20. F 10/31 | PS7 | Order statistics / Selection algorithms (Randomized, Quickselect, "Magic Five") | ||
| Week 8: More Divide-and-Conquer; Network Flow | ||||
| 21. M 11/3 | Closest points in the plane | |||
| 22. W 11/5 | PS8 | D&C wrap-up; Network flow, max flow, and applications | PS9 | |
| 23. F 11/7 | PS8 | Max-flow applications; Residual graphs; Ford–Fulkerson | ||
| Week 9: Network Flow | ||||
| 24. M 11/10 | F–F complexity; Cuts in Flow Networks; Max Flow / Min Cut | |||
| 25. W 11/12 | PS9 | Max Flow / Min Cut redux; Edmonds–Karp | PS10 | |
| 26. F 11/14 | PS9 | Image Segmentation via Max Flow | ||
| Week 10: Wrap-Up | ||||
| 27. M 11/17 | PS10 | Local Search | ||
| 28. W 11/19 | PS10, Exam Notes | Gradient Descent & Simulated Annealing; Review; Ask Me Anything; Course evals | ||
| Exam Period | ||||
| Mon. 11/24 | 3a Exam Period: 8:30am–11am (though the final is self-scheduled) | |||