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.