Lecture 1,2 (10,17 March):
Sorting and Selection
Lecture 3 (31 March):
Greedy algorithms and Matroids
Lectures 4 and 5 (7 and 28 of April):
Matchings
Lectures 6 and 7 (12 and 19 and part of 26 of May):
Treewidth and graph minors
Lectures 8 and 9 (part of 26 of May, and June 2):
Spectral graph theory and refutation of random 4SAT
Lecture 10 (June 9):
The local lemma and satisfying sparse k-SAT
Lecture 11 (June 16):
Fast matrix multiplication
Lecture 12 (June 23):
The Permanent and the Determinant
Handouts (homework) for course.
Handout 1 (17 March):
Sorting and Selection
Handout 2 (31 March):
Greedy algorithms and Matroids
Handout 3 (28 April):
Matching
Handout 4 (19 May):
Treewidth and graph minors. Note: this is a new version with revised homework questions.
Handout 5 (2 June):
Spectral graph theory. Note: this is a new version in which question 5 is easier. (If you solved the previous version, thats even better.)
Handout 6 (16 June):
Permanent and Determinants.
If you find errors in lecture notes or handouts, please let me know.