CS 787: Advanced Algorithms

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

• Course Description
• Topics List
• Reference Books

Homework Assignments

• Homework 0 (due Sep 6)
• Homework 1 (due Oct 4)
• Homework 2 (due Nov 1)
• Homework 3 (due Nov 25)

Readings

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