1
 02/06 
Introduction to Randomized Algorithms. Quicksort, BSP. 
NB 
2
 02/08 
Mincut, Complexity theory, Adelman's theorem. 
NB 
3
 02/11 
Game tree evaluation, game theory, lower bounds 1. 
NB 
4
 02/13 
Lower bounds 2, coupon collecting, stable marriage. 
NB 
L04 
5
 02/15 
Deviations: Markov, Chebyshev. Median finding 1. 
NB 
L05 
6
 02/19 
Median finding 2. Pseudorandom numbers. 
NB 
L06 
(Monday schedule on Tuesday) 
7
 02/20 
Chernoff bound. Randomized routing. 
NB, NB 
L07 
8
 02/22 
Twochoice load balancing 1. 
NB 
L08 
9
 02/25 
Twochoice load balancing 2. Hashing: universal, perfect 1. 
NB 
L09 
10
 02/27 
Hashing: perfect 2, cuckoo, consistent 1. 
NB 
L10 
11
 03/01 
Hashing: consistent 2. Fingerprinting, string matching 1. 
NB 
L11 
12
 03/04 
String matching 2. Bloom Filters. 
NB 
L12 
13
 03/06 
Fingerprinting by polynomials, perfect matching, network coding. 
NB 
L13 
14
 03/08 
Symmetry breaking. Parallel algorithms. Independent set 1. 
NB 
L14 
15
 03/11 
Independent set 2. Derandomization. 
NB 
L15 
16
 03/13 
Isolating Lemma. Perfect Matching. Shortest paths 1. 
NB 
L16 
17
 03/15 
Shortest paths 2. 
NB 
L17 
18
 03/18 
Sampling: polling. Streaming algorithms: frequent items, sketches, distinct items. 
NB, NB 
19
 03/20 
Rare events. DNF counting. Counting versus generation. Minimum spanning tree. 
20
 03/22 
Recursive contraction (with mincuts). Graph sparsification. Minimum cut. 
 03/25 



 03/27 
No lecture 


(Spring vacation) 
 03/29 



21
 04/01 
Network reliability. Geometry. 
22
 04/03 
Arrangements of lines. Randomized incremental construction: convex hull. 
23
 04/05 
Sampling for LP. Iterative reweighting. Randomized incremental construction. Hidden dimension. 
24
 04/08 
Randomized rounding: maxcut, maxSAT. 
25
 04/10 
Randomized rounding 2: set bias, wiring, derandomization. 
26
 04/12 
Maxcut by semidefinite programming (SDP). Begin bisection/separator. 
 04/15 
No lecture 


(Patriots' Day vacation) 
27
 04/17 
Embeddings. Ratio cut. 
28
 04/19 
Markov chains 1. 
29
 04/22 
Markov chains 2. Expanders. 
30
 04/24 
Markov chains 3: sampling. 
31
 05/15 
Peer editing session. 


(Required attendance!!) 
 05/16 
 


(Last day of classes) 