CS7800: Advanced Algorithms

Syllabus

Schedule

Assignments

Notes:

# Date Topic Reading
1 F 9/8 Course Overview, Stable Matching ---
2 T 9/12 Greedy Algorithms: Interval Scheduling, Minimizing Lateness KT 4.1-4.3
KT 1-3
3 F 9/15 Greedy Algorithms: Shortest Paths, Minimum Spanning Trees KT 4.4-4.6
4 T 9/19 Divide-and-Conquer Algorithms: Counting Inversions, Selection, Closest Pair KT 5.1-5.4
Optional: Erickson 1.7
5 F 9/22 Divide-and-Conquer: Integer Multiplication and FFT KT 5.5-5.6
6 T 9/26 Dynamic Programming: Weighted Interval Scheduling KT 6.1-6.2
7 F 9/29 Dynamic Programming: Finish Basic Techniques KT 6.3-6.5
Optional: Erickson 5
8 T 10/3 Dynamic Programing: Edit Distance / Alignments, Shortest Paths KT 6.6-6.10
Optional: Erickson 6.1
9 F 10/6 Network Flow: Basic Concepts, Duality, Ford-Fulkerson Algorithm KT 7.1-7.2
10 T 10/10 Network Flow: Choosing Good Paths KT 7.3-7.4
11 F 10/13 Network Flow: Applications, Wrap-Up KT 7.5-7.6
KT 7.7-7.13
12 T 10/17 No Class ---
13 F 10/20 Midterm (tentative) ---