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 

7
 03/03 
Randomized routing. 
NB 
L07 

8
 03/05 
The Power of Two Choices 
NB 
L08 

 
Below this point is subject to change

9
 03/09 
Twochoice load balancing 2. Hashing: universal, perfect 1. 
NB 
L09 

(Monday schedule on Tuesday) 
10
 03/10 
Hashing: perfect 2, cuckoo, consistent 1. 
NB 
L10 

11
 03/12 
Hashing: consistent 2. Fingerprinting, string matching 1. 
NB 
L11 

12
 03/15 
String matching 2. Bloom Filters. 
NB 
L12 

13
 03/17 
Fingerprinting by polynomials, perfect matching, network coding. 
NB 
L13 

14
 03/19 
Symmetry breaking. Parallel algorithms. Independent set 1. 
NB 
L14 

 03/22 
No lecture 



(Student Holiday) 
15
 03/24 
Independent set 2. Derandomization. 
NB 
L15 

16
 03/26 
Isolating Lemma. Perfect Matching. Shortest paths 1. 
NB 
L16 

17
 03/29 
Shortest paths 2. 
NB 
L17 

18
 03/31 
Sampling: polling. Streaming algorithms: frequent items, sketches, distinct items. 
NB, NB 
L18 

19
 04/02 
Sampling: transitive closure. DNF counting, rare events. 
NB, NB 
L19 

20
 04/05 
Counting versus generation. Minimum spanning tree 1. 
NB, NB 
L20 

21
 04/07 
Minimum spanning tree 2. Mincuts: recursive contraction algorithm 1. 
NB, NB 
L21 

22
 04/09 
Min cuts: recursive contraction algorithm 2, graph sparsification 1. 
NB 
L22 

23
 04/12 
Min cuts: graph sparsification 2. Network reliability 1. 
NB 
L23 

24
 04/14 
Network realiability 2. Arrangements of lines 1. 
NB, NB
 L24 

25
 04/16 
Arrangements of lines 2. Convex hull via randomized incremental construction. 
NB 
L25 

 04/19 
No lecture 



(Patriots' Day vacation) 
26
 04/21 
LP: sampling, randomized incremental construction. 
NB 
L26 

27
 04/23 
LP: iterative reweighting, hidden dimension, simplex. 
NB 
L27 

28
 04/26 
Randomized rounding: maxcut, set balancing, set cover, routing/wiring, derandomization. 
NB, NB 
L28 

29
 04/28 
Semidefinite programming: maxcut, embeddings, graph coloring. Markov chains 1. 
NB, NB 
L29 

30
 04/30 
Markov chains 2: random walks. 
NB 
L30 

31
 05/03 
Markov chains 3: bipartite matching, sampling, and MCMC. 
NB, NB 
L31 

32 
05/05 
Peer editing session. 



(Required attendance!!) 
 05/20 
 



(Last day of classes) 