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
RandomizedAlgorithms. What they are and what we will do with them. Readings: §§1.1–1.2, 1.5.
ProbabilisticRecurrences. Readings: §1.4.
RandomizedLowerBounds: minimax principles and Yao's lemma, Adleman's theorem. Readings: §2.1–2.2.
Make-up lecture in AKW 200. More ProbabilisticInequalities: Chernoff bounds. Readings: §4.1.
Review session by NicholasRuozzi.
Martingales: basics. Readings: §4.4.
Martingales: how zero-mean martingales act like sums of independent random variables. The Azuma-Hoeffding inequality and the method of bounded differences.
Martingales and stopping times. The optional stopping theorem.
More Martingales: submartingales and supermartingales.
MarkovChains: definition, classification of states, convergence. Readings: §§6.1–6.2.
More reversible MarkovChains: Conductance and canonical paths.
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.
Randomized data structures: RandomizedSearchTrees, skip lists. Readings: §§8.1–8.3.
More randomized data structures: HashTables. Readings: §§8.4–8.5.
Start of OnLineAlgorithms: The list update problem. Readings: Chapter 13.
More OnLineAlgorithms: Paging.
Randomized distributed algorithms; RandomizedConsensus. Readings: see notes.