Advanced Course on Algorithms, March 2004 - June 2004

by Uri Feige

Take-home exam 2 of June, 2004. Hand in by 2 of July, 2004. Note: most main ideas of the solution appear in the lecture notes for lecture 11 (but you are required to write then in your own words, fill in missing proofs, etc.). Others should have appeared in the lecture notes for lecture 8, but the corresponding sections were not written.
Remarks on take-home exam July, 2004.

Lecture notes:

Lectures 1 and 2, 3 and 10 of March, 2004: Edmonds' algorithm for maximum cardinality matching. Maximum weight bipartite matching.
Lectures 3 and part of 4, 17 and 24 of March, 2004: The linear algebra of linear programming. The Beck-Fiala theorem.
Lectures 4 and 5 (parts), 24 and 31 of March, 2004: The geometry of linear programming.
Lectures 5 (parts) and 6, 31 of March and 14 of April, 2004: The simplex algorithm.
Lecture 7, 21 of April, 2004: Linear programming duality.
Lecture 8, 28 of April, 2004 (+ some of May 19): The ellipsoid algorithm.
Lecture 9, 5 of May, 2004: Randomized algorithms for linear programming (given by Moni Naor).
Lecture 10, 12 of May, 2004 (+ some of May 19): Applications of LP duality.
Lecture 11, 2 of June, 2004: Perfect graphs and the theta function of Lovasz.

Handouts (homework) for course.

Handout 1, 3 March 2004: matching.
Handout 2, 10 March 2004: matching.
Handout 3, 24 March 2004: linear programming.
Handout 4, 14 April 2004: The simplex algorithm.
Handout 5, 21 April 2004: Linear programming duality.
Handout 6, 12 May 2004: Applications of LP duality.

If you find errors in lecture notes or handouts, please let me know.