Course on Algorithms and their analysis, October 1999 - February 2000

by Uri Feige


Final exam, February 10, 2000 and solutions to final exam.

Lecture notes:

Lecture 1, 21 October 1999: quicksort and its analysis, "Las Vegas" algorithms.
Lecture 2, 28 October 1999: dynamic programming, fixed parameter versions of NP-hard optimization problem on graphs, bisection.
Lecture 3, 4 November 1999: dynamic programming, longest path, bandwidth.
Lecture 4, 11 November 1999: dynamic programming on trees, tree-width, graph minors.
Lecture 5, 18 November 1999: inductive coloring, coloring graphs of bounded tree-width, the excluded minors theorem and its algorithmic consequences.
Lecture 6, 25 November 1999: fast matrix multiplication.
Lecture 7, 2 December 1999: all pairs shortest paths.
Lecture 8, 9 December 1999: witnesses for Boolean matrix multiplication, testing matrix multiplication. Greedy algorithms for simple scheduling problems.
Lecture 9, 16 December 1999: matroids and greedy algorithms, matroid duality, Euler's formula for planar graphs.
Lecture 10, 23 December 1999: Edmonds' algorithm for maximum cardinality matching. No lecture notes on this subject.
Lecture 11, 30 December 1999: the greedy approximation algorithm for set cover and Christofides' algorithm for approximating metric TSP.
Lecture 12, 6 January 2000: Fast Fourier Transform, multiplying polynomials, interpolating a polynomial from its roots. No lecture notes on this subject.
Lecture 13, 13 January 2000: minimum cuts in graphs via random contractions. Randomized approximation of domatic number.
Lecture 14, 20 January 2000: method of conditional expectations. Algorithms in number theory.
Lecture 15, 3 February 2000: algorithms in number theory. Diffie-Hellman key exchange. RSA.

Handouts (homework) for course. Slightly edited so as to correct errors.

Handout 1, 21 October 1999: quicksort.
Handout 2, 28 October 1999: dynamic programming.
Handout 3, 11 November 1999: graph minors and bounded tree-width.
Handout 4, 25 November 1999: matrix operations.
Handout 5, 9 December 1999: greedy algorithms.
Handout 6, 16 December 1999: matroids.
Handout 7, 23 December 1999: matchings.
Handout 8, 30 December 1999: approximation algorithms.
Handout 9, 6 January 2000: Fast Fourier Transform.
Handout 10, 13 January 2000: two randomized algorithms.
Handout 11, 20 January 2000: Method of conditional probabilities; number Theory.

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


ADDITIONAL LECTURE NOTES AND HANDOUTS, 2001-2002.

Lectures 7 and 8, 2 and 9 of January, 2002: Edmonds' algorithm for maximum cardinality matching. Maximum weight bipartite matching.
Handout 8, 9 January 2002: Matchings continued.
Final exam, 13 March 2002.
Solution to final exam . (Prepared by Eran Tromer.)


ADDITIONAL LECTURE NOTES AND HANDOUTS, 2009-2010.

Lectures 9 and 10, 30 of December, 2009, 6 January 2010: The permanent and the determinant. Ryser's formula, Lovasz's randomized perfect matching algorithm, the tree-matrix theorem.
Lectures 10-12, January 2010: Spectral graph theory. Refuting random 4CNF formulas.
Lecture 13, 27 January 2010: The Lovasz Local Lemma. Satisfying sparse k-SAT. Moser's algorithmic version.

Lecture 14, 3 February 2010: Summary, practice questions and hints.