Course on Algorithms and their analysis, November 2017 - February 2018

by Uri Feige


No class on November 16.

Lecture notes. Initially the links point to lecture notes from the course given at 2014, and as the course progresses, some lecture notes are replaced by new updated ones.

Lecture 1,2 (2, 9 November 2017): Sorting and Selection
Lecture 3 (31 March 2014): Greedy algorithms and Matroids
Lectures 4 and 5 (7 and 28 of April 2014): Matchings
Lectures 6 and 7 (12 and 19 and part of 26 of May 2014): Treewidth and graph minors
Lectures 8 and 9 (part of 26 of May, and June 2, 2014): Spectral graph theory and refutation of random 4SAT
Lecture 10 (June 9, 2014): The local lemma and satisfying sparse k-SAT
Lecture 11 (June 16, 2014): Fast matrix multiplication
Lecture 12 (June 23, 2014): The Permanent and the Determinant

Handouts (homework) for course. Initially the links point to handouts from the course given at 2014, and as the course progresses, all handouts are replaced by new updated ones.

Handout 1 (9 November 2017): Sorting and Selection
Handout 2 (31 March 2014): Greedy algorithms and Matroids
Handout 3 (28 April 2014): Matching
Handout 4 (19 May 2014): Treewidth and graph minors. Note: this is a new version with revised homework questions.
Handout 5 (2 June 2014): 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 2014): Permanent and Determinants.

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