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.