CS 761
Course notes
Lecture 1 (May 1): Introduction [pdf, one]

Lecture 2 (May 3): Tail inequalities [pdf, one]

Lecture 3 (May 8): Graph algorithms [pdf, one]

Lecture 4 (May 10): Approximation algorithms [pdf, one]

Lecture 5 (May 15): Balls and bins [pdf, one] (updated May 15)

Lecture 6 (May 17): Hashing [pdf, one]

Lecture 7 (May 24)

Lecture 8 (May 29): Data streaming [pdf, one]

Lecture 9 (May 31): Polynomial identity testing [pdf, one]

Lecture 10 (Jun 12): Network coding [pdf, one]

Lecture 11 (Jun 14): Interactive proofs [pdf, one]

Lecture 12 (Jun 19): Probabilistic methods [pdf, one]

Lecture 13 (Jun 21): Entropy [pdf, one]

Lecture 14 (Jun 26)

Lecture 15 (Jun 28): Local lemma [pdf, one]

Lecture 16 (July 3): Random walks on directed graphs [pdf, one]

Lecture 17 (July 5): Random walks on undirected graphs [pdf, one]

Lecture 18 (July 10): Mixing time [pdf, one]

Lecture 19 (July 12)

Lecture 20 (July 17): Markov chain Monte Carlo [pdf, one]

Lecture 21 (July 19): Coupling [pdf, one]

Lecture 22 (July 24): Metric embedding [pdf, one]

Lecture 23 (July 26): Randomized linear algebra [pdf, one]
