Homework assignments are due at 12:15pm 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 9/16 | Welcome Being Bad At Math |
PS1 | Preface, §1.1, §2.1–2 | ||
| 2. W 9/18 | PS1.I | State health-care emulation; Solving stable matching: brute-force and the Gale–Shapley proposal algorithm | PS2 | §2.3–5 | |
| 3. F 9/20 | PS1.II | Gale–Shapley; stable-matching variants that better model the NRMP | §3.1 Optionally (but skim pages 1–3), read Jack Edmonds, Paths, Trees, and Flowers. Canadian Journal of Mathematics, 1965 |
||
| Week 2: Asymptotics, Proofs of Correctness, and Graphs | |||||
| 4. M 9/23 | PS2.I | Stable matching wrapup; data structures; asymptotics | Posted asymptotics notes; §1.2; §3.2–3 | ||
| 5. W 9/25 | PS2.II | Asymptotics (O, Ω, Θ) | PS3 | §3.4–6 | |
| 6. F 9/27 | PS2.III | Graph representations; sample problems | §4.4 | ||
| Week 3: Greedy Algorithms | |||||
| 7. M 9/30 | PS3.I | DFS; BFS; "edge explosion"; Dijkstra's algorithm | §4.1 | ||
| 8. W 10/2 | PS3.II | Dijkstra implementation; greedy algorithms; interval scheduling | PS4 | §4.2 | |
| 9. F 10/4 | PS3.III | Interval scheduling; deadline scheduling; exchange arguments | §4.5–6 | ||
| Week 4: More Greedy Algorithms; Dynamic Programming | |||||
| 10. M 10/7 | PS4.I | MSTs: Reverse-Delete, Kruskal's, and Prim's Algorithms; MST properties | |||
| 11. W 10/9 | PS4.II | Implementing Kruskal's; Disjoint Set / Union-Find data structures; Intro to Dynamic Programming | Optional: Jeff Erickson's notes on Disjoint Sets data structures | ||
| 12. F 10/11 | PS4.III | Borůvka's MST algorithm; D.P.: word segmentation | PS5 | §6.1–2 Optional: David Karger, Philip Klein, and Robert Tarjan. A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees. JACM, 1995. |
|
| Week 5: Dynamic Programming | |||||
| 13. M 10/14 | Word segmentation, weighted interval scheduling; course evals | ||||
| 14. W 10/16 | Exam 1 | PS6 | §6.6–8 | ||
| 15. F 10/18 | PS5.I | D.P. smörgåsbord: sequence alignment, seam carving, shortest paths with negative edges | Optional: the rest of chapter 6 (D.P.) | ||
| Week 6: Dynamic Programming Redux | |||||
| XX. M 10/21 | No class (like a Marxist utopia) | ||||
| 16. W 10/23 | PS6.I | Sequence alignment, seam carving | PS7 | §5.1–2, The original demo video for Seam Carving, from SIGGRAPH 2007 | |
| 17. F 10/25 | PS6.II | D.P. Shortest-path algorithms: Bellman–Ford and Floyd–Warshall | §5.3 | ||
| Week 7: Divide-and-Conquer | |||||
| 18. M 10/28 | PS7.I | Divide-and-Conquer intro; recurrence relations | §5.4; handouts on inversions and order statistics (on Moodle) | ||
| 19. W 10/30 | PS7.II | Counting inversions; order statistics | The Wikipedia article on selection algorithms, handouts on Magic Five and Closest-Points (on Moodle) | ||
| 20. F 11/1 | PS7.III | Selection algorithms (Quickselect, randomized, "Magic Five"); Closest points in the plane | PS8 | §7.1 | |
| Week 8: Network Flow | |||||
| 21. M 11/4 | D&C wrap-up; Network flow and cuts | §7.2–3 | |||
| 22. W 11/6 | PS8.I | Max flow; Ford–Fulkerson | §7.5 | ||
| 23. F 11/8 | PS8.II | Max flow / min cut | PS9 | ||
| Week 9: More Network Flow, Etc. | |||||
| 24. M 11/11 | PS8.III | Max flow / min cut; Edmonds–Karp | |||
| 25. W 11/13 | Exam 2 | §8.0, §8.3, §9.1, P vs. NP on Wikipedia | |||
| 26. F 11/15 | PS9.I | Bipartite Matching; looking forward to CS 254 | |||
| Week 10: Etc., Etc. | |||||
| 27. M 11/18 | PS9.II | Mystery class; review | |||
| 28. W 11/20 | Ask me anything; course evals | ||||