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 
L18 
19
 03/20 
Sampling: transitive closure. DNF counting, rare events. 
NB, NB 
L19 
20
 03/22 
Counting versus generation. Minimum spanning tree 1. 
NB, NB 
L20 
 03/25 



 03/27 
No lecture 


(Spring vacation) 
 03/29 



21
 04/01 
Minimum spanning tree 2. Mincuts: recursive contraction algorithm 1. 
NB, NB 
L21 
22
 04/03 
Min cuts: recursive contraction algorithm 2, graph sparsification 1. 
NB 
L22 
23
 04/05 
Min cuts: graph sparsification 2. Network reliability 1. 
NB 
L23 
24
 04/08 
Network realiability 2. Arrangements of lines 1. 
NB, NB
 L24 
25
 04/10 
Arrangements of lines 2. Convex hull via randomized incremental construction. 
NB 
L25 
26
 04/12 
LP: sampling, randomized incremental construction. 
NB 
L26 
 04/15 
No lecture 


(Patriots' Day vacation) 
27
 04/17 
LP: iterative reweighting, hidden dimension. Randomized rounding: maxcut, maxSAT, set bias, wiring, derandomization. 
 04/19 

 04/22 
No lecture 


(Independent time for project) 
 04/24 

 04/26 

28
 04/29 
Maxcut by semidefinite programming (SDP). Begin bisection/separator. Embeddings. Ratio cut. 
29
 05/01 
Markov chains 1. 
30
 05/03 
Markov chains 2: expanders. 
31
 05/06 
Markov chains 3: sampling. 
32 
05/15 
Peer editing session. 


(Required attendance!!) 
 05/16 
 


(Last day of classes) 