CS 787: Advanced Algorithms

MWF 9:55 - 10:45
1325 CS

Instructor: Eric Bach

     Office : 4391 CS
     Phone : 262 7997
     E-mail : famous baroque composer ampersand cs dot wisc dot edu
     Office Hours: MWF 11:00-12:00

General Course Information

Homework Assignments and Handouts

Readings

Gale and Shapley on stable marriages W 1/25/23
Manber on designing algorithms using induction F 1/27/23
Cauchy on the arithmetic-geometric mean inequality M 1/30/23
Karatsuba on fast multiplication M 1/30/23
Pruhs on dynamic programming W 2/1/23
Pollard on the kangaroo method F 2/3/23, M 2/6/23
Karp on linear programming W 2/8/23, F 2/10/23, M 2/13/23
Duality cheat sheet M 2/13/23
Chvatal on the set cover problem W 2/15/23
Papadimitriou and Steiglitz on shortest paths F 2/17/23
Tarjan on network flow M 2/20/23 F 2/24/23
Edmonds and Karp on efficiently solving flow problems M 2/27/23
Wayne on baseball elimination W 3/1/23
Vazirani on matchings and coverings F 3/3/23
Ford and Fulkerson on Koenig's theorem F 3/3/23
Notes on the assignment problem M 3/6/23 W 3/8/23
Notes on the primal-dual method F 3/10/23
Using primal-dual for a transportation problem M 3/20/23
Williamson on primal-dual approximations W 3/22/23
Hoffman on greedy linear programs F 3/24/23
Edmonds on the greedy algorithm M 3/27/23
Lawler (Sections 7.1-7.8) on matroids W 3/29/23 F 3/31/23
Spencer on a Ramsey number lower bound M 4/3/23
Schwartz on randomized identity testing M 4/3/23
Finite fields and square roots mod p W 4/5/23
Mulmuley, Vazirani, and Vazirani on matching F 4/7/23 M 4/10/23
Ta-Shma on the isolation lemma W 4/12/23
Raghavan and Thompson on randomized rounding F 4/14/23
Goemans and Williamson on maximum satisfiability M 4/17/23
Notes on convexity W 4/19/23
Lovasz on semidefinite programming F 4/21/23, W 5/3/23
Goemans and Williamson on maximum cut M 4/24/23
Lawler on ellipsoids and factoids W 4/26/23
Aspvall and Stone on the ellipsoid algorithm W 4/26/23 -- M 5/1/23
Notes on Lagrangian Relaxation F 5/5/23