Spring 2022: MWF 2:00 pm -- 2:50 pm, Lecture Center C (LCC) C006
| Week | Date | Topic | Reading | Notes |
|---|---|---|---|---|
| 1 | M. 1/10 | Course Introduction |
Course Syllabus
Course Topics |
|
| W. 1/12 | Intro and Review; Stable matching | KT 1 |
Course Introduction
KT: Intro (Stable matching) KT: Stable matching demo |
|
| F. 1/14 | Stable matching | KT 1 | ||
| 2 | W. 1/19 | Stable matching | KT 1 | Class notes |
| F. 1/21 | Analysis and Design | KT 2 |
KT: Analysis of Algorithms
Combinarorial cheat sheet |
|
| 3 | M. 1/24 | Analysis and Design | KT 2 | Class notes |
| W. 1/26 | Analysis and Design | KT 2 | Class notes | |
| F. 1/28 | Graphs | KT 3, CLSR VI-1 | KT: Graphs | |
| 4 | M. 1/31 | Graphs | KT 3, CLSR VI-1 | Class notes |
| W. 2/2, F. 2/4 | Graphs | KT 3, CLSR VI-1 | ||
| 5 | M. 2/7 | Greedy Algorithms Part I | KT 4.1 | KT: Greedy algoritms |
| W. 2/9,F. 2/11 | Greedy Algorithms Part I | KT 4.2, 4.3 | HW1 Solution | |
| 6 | M. 2/14, W. 2/16,F. 2/18 | Greedy Algorithms Part II | KT 4.4, 4.5; CLRS VI-(2,3,4) |
KT: Greedy algoritms, continued
Jeff Erikson: MST, a different view Class Notes |
| 7 | M. 2/21 | Greedy Algorithms Part II; Divide and conquer | KT 4.4, 4.5; CLRS VI-(2,3,4); KT 5 | KT:Divide and conquer |
| W. 2/23, F. 2/25 | Divide and conquer | KT 5 | ||
| 8 | M. 2/28 | Divide and conquer | KT 5 | |
| W. 3/2 | Dynamic Programming: Intro | KT 6.1, 6.2; CLRS VII-28 | Dynamic programming
Notes on Recurrences (Fibonacci numbers) |
|
| F. 3/4 | Course Review | HW2-Solution | ||
| 9 | M 3/7 | MIDTERM EXAM 1 | ||
| W 3/9, F 3/11 | Dynamic Programming: Weighted Job Scheduling | KT 6.1, 6.2; CLRS VII-28 | ||
| 10 | M 3/14, W 3/16, F 3/18 | Dynamic Programming: Segmented Line SE; 0/1 Knapsack | KT 6.3, 6.4; CLRS VII-28 | Class Notes |
| F 3/18 | Dynamic Programming: RNA Secondary Sequence | KT 6.5 | ||
| 11 | M 3/28 | Dynamic programming: Sequence Alignment | KT 6.6, KT 6.7 | Class Notes |
| W 3/30, F 4/1 | Dynamic programming: Bellman-Ford | KT 6.8, 6.9, 6.10 | Bellman-Ford shortest paths | |
| 12 | M 4/4 | Dynamic programming: Bellman-Ford | KT 6.8, 6.9, 6.10 | Class Notes |
| W 4/6,F 4/7 | Netowrk Flow | KT 7.1, 7.2; CLRS 26.1 |
Network flow, Network flow demo
HW3-solution, HW3-solution-cycle |
|
| 13 | M 4/11 | MIDTERM EXAM 2 | ||
| 13 | W 4/13, F 4/15 | Network Flow | KT 7.1, 7.2, 7.3, 7.4; CLRS 26.1,2 | Class Notes |
| 14 | M 4/18 | Network Flow Applications: Bipartite Matching, Disjoint Paths, Extensions to Max Flow | KT 7.5, 7.6,7.7, 7.8; CLRS 26.3 | Network flow applications |
| W 4/20 | Network Flow Applications: Circulations with Demand/Lower-bound, Image Segmentation | KT 7.5, 7.6,7.7, 7.8; CLRS 26.3 | Network flow applications | |
| F 4/22 | NP completeness and intractability | KT 8.1; CLRS 34-1,2 | Poly time reductions | |
| 15 | M 4/25, W 4/27 | Poly time reductions: 3SAT, MIS, V-C | KT 8.1,2,3; CLRS 34 | Reductions via gadgets: 3-SAT to Independent Set
Efficient certifiers and definition of NP Class Notes |
| F 4/29 | Final Review | |||
| W 5/4 | Final Exam | 1:00 pm -- 3:00 pm; Lecture Center C (LCC) C006 |