1
 02/17 
Introduction to Randomized Algorithms. Quicksort, BSP. 
NB 
L01 
L01 
2
 02/19 
Mincut, Complexity theory, Adelman's theorem. 
NB 
L02 
L02 
3
 02/22 
Game tree evaluation, game theory, lower bounds 1. 
NB 
L03 
L03 
4
 02/24 
Coupon Collecting, Stable Marriage, and Deviations 1 
NB 
L04 
L04 
5
 02/26 
Deviations: Markov, Chebyshev. Median finding 1. 
NB 
L05 
L05 
6
 03/01 
Pseudorandom numbers. Chernoff bound. 
NB, NB 
L06 
L06 
7
 03/03 
Randomized routing. 
NB 
L07 
L07 
8
 03/05 
The Power of Two Choices 
NB 
L08 
L08 
9
 03/09 
Hashing 
NB, NB 
L09 
L09 
(Monday schedule on Tuesday) 
10
 03/10 
Hashing 2 
NB 
L10 
L10 
11
 03/12 
Fingerprinting 
NB 
L11 
L11 
12
 03/15 
Bloom Filters, Fingerprinting by polynomials, perfect matching. 
NB, NB 
L12 
L12 
13
 03/17 
Perfect matching, network coding, symmetry breaking. 
NB 
L13 
L13 
14
 03/19 
Symmetry breaking. Parallel algorithms. Independent set. 
NB 
L14 
L14 
 03/22 
No lecture 



(Student Holiday) 
15
 03/24 
Shortest Paths. 
NB 
L15 
L15 
16
 03/26 
Isolating Lemma. Perfect Matching. Shortest paths 1. 
NB 
L16 
L16 
17
 03/29 
Sampling: polling. Streaming algorithms: frequent items, sketches, distinct items. 
NB, NB 
L17 

18
 03/31 
Sampling: transitive closure. DNF counting, rare events. 
NB, NB 
L18 
L18 
19
 04/02 
Counting versus generation. Minimum spanning tree 1. 
NB 
L19 
L19 
20
 04/05 
Minimum spanning tree 2. Mincuts: recursive contraction algorithm 1. 
NB, NB 
L20 
L20 
21
 04/07 
Mincuts: recursive contraction algorithm 2. Sampling Minimum Cuts. 
NB 
L21 
L21 
22
 04/09 
Sampling Cuts 
NB 
L22 
L22 
23
 04/12 
Network reliability. 
NB 
L23 
L23 
24
 04/14 
Arrangements of lines. Convex hull via randomized incremental construction 1. 
NB
 L24 
L24 
25
 04/16 
Convex hull via randomized incremental construction 2. LP: sampling. 
NB, NB 
L25 
L25 
 04/19 
No lecture 



(Patriots' Day vacation) 
26
 04/21 
Sampling for LP. 
NB 
L26 
L26 
27
 04/23 
LP: simplex. Random Answers. 
NB, NB 
L27 
L27 
28
 04/26 
Randomized rounding. 
NB, NB 
L28 
L28 
29
 04/28 
Embeddings. 
NB 
L29 

30
 04/30 
Metric Embeddings 2. 
NB 
L30 

31
 05/03 
Metric Embeddings; Markov chains 1. 
NB, NB 
L31 

32
 05/05 
Markov chains 2: random walks. 
NB 
L32 

 
Below this point is subject to change

33 
05/14 
Peer editing session. 



(Required attendance!!) 
 05/20 
 



(Last day of classes) 