Syllabus |
Schedule |
| # | Date | Topic | Reading | HW |
|---|---|---|---|---|
| 1 | Mon 1/6 | Welcome! Slides |
--- | HW1 Out: pdf, tex Due Fri 1/17 |
| 2 | Wed 1/8 | Divide and Conquer: Mergesort, Asymptotic Analysis Slides |
KT 5.1, 2.1-2.2 | --- |
| 3 | Mon 1/13 | Divide and Conquer: Karatsuba's Algorithm, Recurrences Slides: Before Class, After Class |
KT 5.2, 5.5 Erickson II.1-3 |
--- |
| 4 | Wed 1/15 | Divide and Conquer: Selection, Binary Search Slides: Before Class, After Class |
Erickson 1.5-1.7 | HW2 Out: pdf, tex Due Fri 1/24 |
| - | Mon 1/20 | No Class (MLK Day) | --- | --- |
| 5 | Wed 1/22 | Dynamic Programming: Key Concepts, Interval Scheduling Slides: Before Class, After Class |
KT 6.1-6.2 | HW3 Out: pdf, tex Due Fri 1/31 |
| 6 | Mon 1/27 | Dynamic Programming: Segmented Least Squares, Adding Variables Slides: Before Class, After Class |
KT 6.3-6.4 | --- |
| 7 | Wed 1/29 | Dynamic Programming: Knapsack, Edit Distance Slides: Before Class, After Class |
KT 6.6-6.7 | HW4 Out: pdf, tex Due Fri 2/7 |
| 8 | Mon 2/3 | Dynamic Programming: More Examples Slides: Before Class, After Class |
--- | --- |
| 9 | Wed 2/5 | Graph Algorithms: Key Definitions, DFS Slides: Before Class, After Class |
KT 3.1-3.3, 3.5-3.6 | --- |
| - | Mon 2/10 | No Class (Illness) | --- | --- |
| - | Wed 2/12 | Midterm I (In Class) | --- | --- |
| - | Mon 2/17 | No Class (President's Day) | --- | --- |
| 10 | Wed 2/19 | Graph Algorithms: Finish DFS, Topological Sort Slides: Before Class, After Class |
KT 3.4 | HW5 Out: pdf, tex Due Fri 2/28 |
| 11 | Mon 2/24 | Shortest Paths: BFS, Start Dijkstra Slides: Before Class, After Class |
KT 3.4, 4.4, 2.5 | --- |
| 12 | Wed 2/26 | Shortest Paths: Finish Dijkstra, Bellman Ford Slides: Before Class, After Class |
KT 6.8-6.10 | HW6 Out: pdf, tex Due Fri 3/20 |
| - | Mon 3/2 | No Class (Spring Break) | --- | --- |
| - | Wed 3/4 | No Class (Spring Break) | --- | --- |
| 13 | Mon 3/9 | Graph Algorithms: Minimum Spanning Trees Slides: Before Class, After Class |
KT 4.5-4.6 | --- |
| 14 | Wed 3/11 | Network Flow: Flows, Cuts, Augmenting Paths Slides: Before Class, After Class |
KT 7.1-7.2 | HW7 Out: pdf, tex Due Fri 3/27 |
| - | Mon 3/16 | No Class (All Hell Broke Loose) | --- | --- |
| 15 | Wed 3/18 | Network Flow: Choosing Good Augmenting Paths Lecture Recording |
Erickson 23.6 | --- |
| 16 | Mon 3/23 | Applications of Network Flow: Reductions, Bipartite Matching Lecture Recording, Slides |
KT 7.5-7.6 | --- |
| 17 | Wed 3/25 | Applications of Network Flow: More Applications Before Class, After Class, Lecture Recording |
KT 7.8-7.12 | --- |
| 18 | Mon 3/30 | Greedy Algorithms: Proof Strategies Before Class, After Class, Lecture Recording |
KT 4.1-4.3 | |
| 19 | Wed 4/1 | Midterm II (In Class) | --- | HW8 Out: pdf, zip Due Fri 4/10 |
| 20 | Mon 4/6 | No Class (Technical Difficulties) | --- | --- |
| 20 | Wed 4/8 | Greedy Algorithms: Huffman Codes Before Class, After Class, Lecture Recording |
KT 4.8 | --- |
| 21 | Mon 4/13 | Stable Matching Before Class, After Class, Lecture Recording |
KT 1.1 | --- |
| - | Fri 4/24 | Final Exam: 8am-10am Location TBD | --- | --- |