Homework assignments are due at 10:30am on the day indicated. Assignments are posted to Moodle. The reading assigned each day relates to the next class's material, and is to be done before the next class meeting. For more details on class policies, please see the syllabus.
| Date | Due | Class Topic and Materials | Out | Reading | |
|---|---|---|---|---|---|
| Week 1: Intro; Stable Matching | |||||
| 1. M 1/6 | Welcome; Course overview; Notation review; Intro to stable matching Being Bad At Math |
PS1 | Preface, §1.1, §2.1–2 | ||
| 2. W 1/8 | PS1.1 | Solving stable matching: brute-force and the Gale–Shapley proposal algorithm | PS2 | §2.3–5 | |
| 3. F 1/10 | PS1.2 | Gale–Shapley | §3.1 Optionally (but skim the first three pages), read Jack Edmonds, “Paths, Trees, and Flowers”, Canadian Journal of Mathematics, 1965 |
||
| Week 2: Asymptotics, Proofs of Correctness, and Graphs | |||||
| 4. M 1/13 | PS2.1 | Stable-matching variants that better model the NRMP; data structures; asymptotics (O, Ω, Θ) | Posted asymptotics notes; §1.2; §3.2–3 | ||
| 5. W 1/15 | PS2.2 | Asymptotics; graphs and graph representations | PS3 | §3.4–6 | |
| 6. F 1/17 | PS2.3 | More on graphs; sample problems | §4.4 | ||
| Week 3: Greedy Algorithms | |||||
| 7. M 1/20 | PS3.1 | DFS; BFS; "edge explosion"; Dijkstra's algorithm | §4.1 | ||
| 8. W 1/22 | PS3.2 | Dijkstra implementation; greedy algorithms; interval scheduling | PS4 | §4.2 | |
| 9. F 1/24 | PS3.3 | Interval scheduling; deadline scheduling | §4.5–6 | ||
| Week 4: More Greedy Algorithms; Dynamic Programming | |||||
| 10. M 1/27 | PS4.1 | Deadline Scheduling & exchange arguments; MSTs: Reverse-Delete, Kruskal's, Prim's, and Borůvka's Algorithms; MST properties | Optional: Jeff Erickson's notes on Disjoint Sets data structures | ||
| 11. W 1/29 | PS4.2 | Implementing Kruskal's; Disjoint Set / Union-Find data structures | Optional: David Karger, Philip Klein, and Robert Tarjan. A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees. JACM, 1995. | ||
| 12. F 1/31 | PS4.3 | Intro to Dynamic Programming; weighted interval scheduling | PS5 | §6.1–2 | |
| Week 5: Dynamic Programming | |||||
| 13. M 2/3 | Weighted Interval Scheduling; course evals | ||||
| 14. W 2/5 | Exam 1 | PS6 | §6.6 | ||
| 15. F 2/7 | PS5.1 | Sequence Alignment | §6.8–9, The original demo video for Seam Carving, from SIGGRAPH 2007 | ||
| Week 6: Dynamic Programming Redux | |||||
| XX. M 2/10 | No class (like a Marxist utopia) | ||||
| 16. W 2/12 | PS6.1 | Problem writeup critique | PS7 | Optional: the rest of chapter 6 (D.P.) | |
| 17. F 2/14 | PS6.2 | Seam Carving; Shortest Paths with negative weights: Bellman–Ford | §5.1–3 | ||
| Week 7: Divide-and-Conquer | |||||
| 18. M 2/17 | DP shortest paths: Floyd–Warshall; Divide-and-Conquer intro; Recurrence relations | §5.4; handouts on inversions and order statistics (on Moodle) | |||
| 19. W 2/19 | PS7.1 | Master theorem; Counting inversions | PS8 | The Wikipedia article on selection algorithms; handout on Magic Five (on Moodle) | |
| 20. F 2/21 | Order statistics / Selection algorithms (Randomized, Quickselect, "Magic Five") | §7.1; handout on Closest-Points (on Moodle) | |||
| Week 8: Network Flow | |||||
| 21. M 2/24 | PS8.1 | Closest points in the plane; D&C wrap-up | §7.2–3 | ||
| 22. W 2/26 | PS8.2 | Network flow; Max flow; Max-flow applications | §7.5 | ||
| 23. F 2/28 | PS8.3 | More Applications; Residual graphs; Ford–Fulkerson | PS9 | ||
| Week 9: More Network Flow | |||||
| 24. M 3/3 | F–F complexity; Cuts in Flow Networks; Max Flow / Min Cut | ||||
| 25. W 3/5 | Exam 2 | ||||
| 26. F 3/7 | PS9.1 | Max flow / min cut redux; Edmonds–Karp | §8.0, §8.3, §9.1, P vs. NP on Wikipedia | ||
| Week 10: Etc. | |||||
| 27. M 3/10 | PS9.2 | Flow wrap-up; Complexity; review | |||
| 28. W 3/12 | PS9.3, Exam Notes | Ask me anything; course evals | |||