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