CS7800: Advanced Algorithms

Syllabus

Schedule

Assignments

Notes:

• Readings in bold are directly relevant to the lecture and are mandatory.
  Other readings are for background / to refresh your memory / for fun. I strongly encourage you to at least skim them.
• This schedule will be updated regularly as the course goes on. Check back here frequently!

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