Syllabus |
Schedule |
| # | Date | Topic | Reading | HW |
|---|---|---|---|---|
| 1 | T 1/9 | Course Overview, Analyzing Algorithms via Induction Slides |
--- | HW1 Out (pdf, tex) |
| 2 | F 1/12 | Asymptotic Analysis, Divide and Conquer: Karatsuba Slides |
KT 2.1-2.2, 5.5 demo |
--- |
| 3 | T 1/16 | Divide and Conquer: Mergesort, Recurrences Slides |
KT 5.1-5.3, demo Erickson II.3 |
--- |
| 4 | F 1/19 | Divide and Conquer: Master Theorem, Medians Slides |
Erickson 1.5-1.7 | HW1 Due HW2 Out (pdf, tex) |
| 5 | T 1/23 | Divide and Conquer: Finish Medians, More Examples Slides |
KT 5.3-5.4 | --- |
| 6 | F 1/26 | Divide and Conquer: Counting Inversions, Closest Pair Slides |
--- | HW2 Due HW3 Out (pdf, tex) |
| 7 | T 1/30 | Dynamic Programming: Basics and Interval Scheduling Slides |
KT 6.1-6.2 | --- |
| 8 | F 2/2 | Dynamic Programming: Segmented Least Squares, Adding Variables Slides |
KT 6.3-6.4 | HW3 Due HW4 Out (pdf, tex) |
| 9 | T 2/6 | Dynamic Programming: Edit Distance Slides |
KT 6.6-6.7 | --- |
| 10 | F 2/9 | Dynamic Programming: More Examples, Midterm Review Slides |
--- | HW4 Due HW5 Out (pdf, tex) |
| -- | T 2/13 | Midterm I (In Class) | --- | --- |
| 11 | F 2/16 | Graph Algorithms: Definitions, BFS Slides |
KT 3.1-3.4 | --- |
| 12 | T 2/20 | Graph Algorithms: BFS Applications, DFS Slides |
KT 3.5-3.6 | --- |
| 13 | F 2/23 | Graph Algorithms: Dijkstra's Shortest Path Algorithm Slides |
KT 4.4, 2.5 | HW5 Due HW6 Out (pdf, tex) |
| 14 | T 2/27 | Graph Algorithms: Minimum Spanning Trees Slides |
KT 4.5-4.6 | |
| 15 | F 3/2 | Graph Algorithms: Bellman-Ford Shortest Paths Slides |
KT 6.8-6.10 | HW6 Due HW7 Out (pdf, tex) |
| -- | T 3/6 | No Class (Spring Break) | --- | --- |
| -- | F 3/9 | No Class (Spring Break) | --- | --- |
| -- | T 3/13 | No Class (Snow Day) | --- | --- |
| 16 | F 3/16 | Network Flow: Flows, Cuts, Ford-Fulkerson Slides |
KT 7.1-7.2 | HW7 Due HW8 Out (pdf, tex) |
| 17 | T 3/20 | Network Flow: Choosing Augmenting Paths Slides |
Erickson 23.6 | --- |
| 18 | F 3/23 | Midterm Review Slides |
--- | HW8 Due |
| -- | T 3/27 | Midterm II (In Class) | --- | --- |
| 19 | F 3/30 | Network Flow Applications: Reductions, Bipartite Matching Slides |
KT 7.5-7.6 | HW9 Out (pdf, tex) |
| 20 | T 4/3 | Network Flow Applications: Image Segmentation, Densest Subgraph Slides |
KT 7.8-7.12 | --- |
| 21 | F 4/6 | Greedy Algorithms Slides |
KT 4.1-4.3 | HW9 Due HW10 Out (pdf, tex) |
| 22 | T 4/10 | Greedy Algorithms: Huffman Codes Slides |
KT 4.8 | --- |
| 23 | F 4/13 | Stable Matching: Gale-Shapley Slides |
--- | --- |
| 24 | T 4/17 | Online Learning: Multiplicative Weights | --- | --- |
| -- | F 4/20 | No Class (Finals Period) | --- | HW10 Due |
| -- | F 4/27 | Final Exam (Location: TBA) | --- | --- |