Syllabus |
Schedule |
Assignments |
Date | Topic | Reading |
---|---|---|
Fri Sep 9 | Welcome. Course overview. Stable marriage. | --- |
Tue Sep 13 | Greedy algorithms: three techniques. | KT 4.1-4.4 Review KT Ch. 1-3 |
Fri Sep 16 | Greedy algorithms: Dijkstra and minimum-spanning tree. | KT 4.4-4.6 |
Tue Sep 20 | Finish greedy. Divide-and-conquer: counting inversions, closest pair. | KT 5.1-5.4 |
Fri Sep 23 | Divide-and-conquer: FFT. | KT 5.5-5.6 |
Tue Sep 27 | Dynamic Programming: Weighted Scheduling, SLS. | KT 6.1-6.3 |
Fri Sep 30 | Dynamic Programming: Knapsack, Edit Distance. | KT 6.4-6.7 |
Tue Oct 4 | Dynamic Programming: Small space edit-distance, shortest paths. | KT 6.8-6.10 |
Fri Oct 7 | Network Flow: Ford-Fulkerson | KT 7.1-7.2 |
Tue Oct 11 | Network Flow: Finish Ford-Fulkerson, capacity scaling Applications: bipartite matching |
KT 7.3, 7.5-7.6 |
Fri Oct 14 | Network Flow: Bipartite matching, edge-disjoint paths, project scheduling | KT 7.5-7.6 |
Tue Oct 18 | No Class | --- |
Fri Oct 21 | Linear Programming: Introduction | Erickson Chapter 26 |
Tue Oct 25 | Linear Programming: Simplex | Erickson Chapter 27 |
Tue Oct 25 | Take-Home Midterm Goes Out @ 5:00pm | --- |
Thu Oct 27 | Take-Home Midterm Due @ 5:00pm | --- |
Fri Oct 28 | Linear Programming: Finish Simplex, Duality | --- |
Tue Nov 1 | NP Completeness: Introduction, Examples | KT 8.1-8.4, 8.7 |
Fri Nov 4 | NP Completeness: More Examples, Wrap-Up | KT 8.8, 9.1,9.2 |
Tue Nov 8 | Finish NP completeness of Subset Sum Randomized Algorithms: Contention Resolution |
KT 13.1, 13.12 |
Fri Nov 11 | No Class---Veterans Day | --- |
Tue Nov 15 | Randomized Algorithms: Global Min-Cut, Linearity of Expectation, Randomized Selection |
KT 13.2, 13.3, 13.5 |
Fri Nov 18 | Randomized Algorithms: String Matching | KT 13.6, Erickson Ch13 |
Tue Nov 22 | No Class---Thanksgiving | --- |
Fri Nov 25 | No Class---Thanksgiving | --- |
Tue Nov 29 | Randomized Algorithms: Chernoff Bounds, Load Balancing | KT 13.9, 13.10 |
Fri Dec 2 | Randomized Algorithms: Hashing | KT 13.6 |
Tue Dec 6 | Wrap-up Randomized Algorithms | --- |
Fri Dec 9 | Approximation Algorithms, Course Wrap-up | Erickson 31.1-31.7 |