Please send me e-mail if you are taking the reading course. Students are encouraged to form small groups and discuss the reading material and associated exercises among themselves. Please update me of your progress (or lack of progress) through e-mail, and schedule meetings to discuss difficulties or if additional explanations are needed (good times can be either Sunday or Wednesday afternoons).

Tentative list of topics for the course:

Greedy algorithms and Matroids.
Exponential time algorithms for graph coloring.
Dynamic programming, treewidth and graph minors.
Average case and smoothed analysis: isolating lemma (knapsack), lattice basis reduction (subset sum).
The local lemma and satisfying sparse k-SAT.
The permanent and the determinant. Tree matrix theorem.
Some applications of linear programming (to be decided).
Spectral graph theory and refutation of random 4SAT.
Some applications of semidefinite programming (to be decided).

Week of April 3. Exponential time algorithms for graph coloring.
Lecture
Homework

Weeks of April 10, April 24. Dynamic programming, treewidth and graph minors.
Lecture
Homework

Weeks of May 1, May 8. The isolating lemma, and lattice basis reductions.
Lecture and homework

(Faculty trip on week of May 15.)
Week of May 22. Algorithmic version of the local lemma.
Lecture and homework

Week of May 29. The permanent and the determinant.
Lecture and homework

Weeks of June 6 and 12. Spectral graph theory and refutation of random 4SAT.
Lecture
Homework

Weeks of June 19 and 26. Fair allocation and linear programming.
Lecture and homework

Week of July 3. Semidefinite programming and max cut.
Lecture: read Sections 6.1 and 6.2 of the book by David Williamson and David Shmoys: The Design of Approximation Algorithms (Cambridge University Press 2011).
A preliminary version of the book, for personal use only and without permission to post this file on any other website, can be obtained from http://www.designofapproxalgs.com/download.php.
Homework