Unless otherwise specified, all readings are in MotwaniRaghavan. As always, the future is uncertain, so you should take parts of the schedule that haven't happened yet with a grain of salt.

1. Detailed schedule

2009-01-12

RandomizedAlgorithms. What they are and what we will do with them. Readings: §§1.1–1.2, 1.5.

2009-01-14

ProbabilisticRecurrences. Readings: §1.4.

2009-01-16

RandomizedLowerBounds: minimax principles and Yao's lemma, Adleman's theorem. Readings: §2.1–2.2.

2009-01-21

Derandomization and Adleman's theorem. Start of ProbabilisticInequalities: Markov's inequality and Chebyshev's inequality. Readings: §2.3, §§3.1–3.3.

2009-01-23

Make-up lecture in AKW 200. More ProbabilisticInequalities: Chernoff bounds. Readings: §4.1.

2009-01-26

Guest lecture by NicholasRuozzi: randomized rounding and set cover; examples of the ProbabilisticMethod (max-SAT, independent sets). Readings: §§5.1–5.2.

2009-01-28

Review session by NicholasRuozzi.

2009-02-02

Martingales: basics. Readings: §4.4.

2009-02-04

Martingales: how zero-mean martingales act like sums of independent random variables. The Azuma-Hoeffding inequality and the method of bounded differences.

2009-02-09

Martingales and stopping times. The optional stopping theorem.

2009-02-11

More Martingales: submartingales and supermartingales.

2009-02-16

MarkovChains: definition, classification of states, convergence. Readings: §§6.1–6.2.

2009-02-18

More MarkovChains: Bounding convergence rates using the coupling method. Readings: Chapter 4-3 of the Aldous-Fill manuscript.

2009-02-23

Reversible MarkovChains.

2009-02-25

More reversible MarkovChains: Conductance and canonical paths.

2009-03-02

Still more MarkovChains: Path coupling, sampling, counting using graph coloring as an example. Side note: The Boyd-Vandenberghe convex optimization book mentioned in class can be found at http://www.stanford.edu/~boyd/cvxbook/. Readings: MitzenmacherUpfal §§11.5–11.6.

2009-03-04

MarkovChain Monte Carlo optimization: The Metropolis-Hastings algorithm and simulated annealing. Readings: MitzenmacherUpfal §10.4.

2009-03-23

The JohnsonLindenstraussTheorem and applications. Readings: Mostly we will be doing the proof in this paper by Dasgupta and Gupta.

2009-03-25

Randomized data structures: RandomizedSearchTrees, skip lists. Readings: §§8.1–8.3.

2009-03-30

More randomized data structures: HashTables. Readings: §§8.4–8.5.

2009-04-01

Fancier HashTables: cuckoo hashing and Bloom filters. Readings: Pagh and Rodler, Cuckoo hashing (see HashTables page for downloadable version), MitzenmacherUpfal §5.5.3.

2009-04-06

KwiseIndependence, plus a quick refresher on FiniteFields. Readings: MitzenmacherUpfal §13.1–13.2.

2009-04-08

DataStreamComputation. Readings: MitzenmacherUpfal §13.4.

2009-04-13

Start of OnLineAlgorithms: The list update problem. Readings: Chapter 13.

2009-04-15

More OnLineAlgorithms: Paging.

2009-04-20

Randomized distributed algorithms; RandomizedConsensus. Readings: see notes.

2009-04-22

BalancedAllocations. Readings: MitzenmacherUpfal Chapter 14.