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