Course on Algorithms and their analysis, March 2014 - June 2014

by Uri Feige

Lecture notes:

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.