Syllabus |
Schedule |
| # | Date | Topic | Reading | HW |
|---|---|---|---|---|
| 1 | F 9/7 | Course Overview Slides: 1:35, 3:25 |
--- | HW1 Out (pdf, tex) |
| 2 | T 9/11 | Stable Matching: Gale-Shapley Algorithm Slides: 1:35, 3:25 |
KT 1.1,1.2,2.3 | --- |
| 3 | F 9/14 | Divide and Conquer: Mergesort, Asymptotic Analysis Slides: 1:35, 3:25 |
KT 5.1, 2.1-2.2 | --- |
| 4 | T 9/18 | Divide and Conquer: Karatsuba, Recurrences Slides: 1:35, 3:25 |
KT 5.2, 5.5 Erickson II.1-3 |
HW1 Due HW2 Out (pdf, tex) |
| 5 | F 9/21 | Divide and Conquer: Selection Slides: 1:35, 3:25 |
Erickson 1.5-1.7 | --- |
| 6 | T 9/25 | Dynamic Programming: Key Concepts, Interval Scheduling Slides: 1:35, 3:25 |
KT 6.1-6.2 | HW2 Due |
| 7 | F 9/28 | Dynamic Programming: Segmented Least Squares, Adding Variables Slides: 1:35, 3:25 |
KT 6.3-6.4 | HW3 Out (pdf, tex) |
| 8 | T 10/2 | Dynamic Programming: Knapsack Slides: 1:35, 3:25 |
KT 6.6-6.7 | --- |
| 9 | F 10/5 | Dynamic Programming: Edit Distance, RNA Folding Slides: 1:35, 3:25 |
--- | HW3 Due HW4 Out (pdf, tex) |
| 10 | T 10/9 | Midterm I Review Slides: 1:35, 3:25 |
--- | --- |
| 11 | F 10/12 | Graph Algorithms: Graphs, BFS Slides |
KT 3.1-3.4 | HW4 Due |
| -- | T 10/16 | Midterm I (In Class) | --- | --- |
| 12 | F 10/19 | Graph Algorithms: 2-Coloring, Connected Components, Topological Sort Slides: 1:35, 3:25 |
KT 3.5-3.6 | HW5 Out (pdf, tex) |
| 13 | T 10/23 | Graph Algorithms: DFS, Start Dijkstra Slides: 1:35, 3:25 |
KT 4.4, 2.5 | --- |
| 14 | F 10/26 | Graph Algorithms: Finish Dijkstra Slides: 1:35, 3:25 |
--- | HW5 Due HW6 Out (pdf, tex) |
| 15 | T 10/30 | Graph Algorithms: Bellman-Ford Slides: 1:35, 3:25 |
KT 6.8-6.10 | --- |
| 16 | F 11/2 | Graph Algorithms: Minimum Spanning Trees Slides: 1:35, 3:25 |
KT 4.5-4.6 | HW6 Due HW7 Out (pdf, tex) |
| 17 | T 11/6 | Network Flow: Flows, Cuts, Augmenting Paths Slides: 1:35, 3:25 |
KT 7.1-7.2 | --- |
| 18 | F 11/9 | Network Flow: Choosing Good Augmenting Paths Slides: 1:35, 3:25 |
Erickson 23.6 | HW7 Due |
| 19 | T 11/13 | Midterm II Review Slides: 1:35, 3:25 |
--- | --- |
| -- | F 11/16 | Midterm II (In Class) | --- | --- |
| -- | T 11/20 | No Class (Thanksgiving Break) | --- | --- |
| -- | F 11/23 | No Class (Thanksgiving Break) | --- | --- |
| 20 | T 11/27 | Network Flow Applications: Reductions, Bipartite Matching Slides: 1:35, 3:25 |
KT 7.5-7.6 | HW 8 Out (pdf, src) |
| 21 | F 11/30 | More Network Flow Applications Slides: 1:35, 3:25 |
KT 7.8-7.12 | --- |
| 22 | T 12/4 | Online Learning: Multiplicative Weights Slides: 1:35, 3:25 |
KT 4.8 | --- |
| --- | F 12/7 | No Class (Just a Placeholder for HW8 Due Date) | --- | HW 8 Due |
| -- | T 12/11 | Final Exam (Time: 1030-1230, Location: 020 West Village F) | --- | --- |