Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

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

2009-01-16

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

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

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