Day  Date  Topic 
Reading Due 
Work Due  
F  Sep 2  PolyEquality & Testing AB=C 

1  M  Sep 5  Probability, Bayes Theorem 
Syllabus 1.11.3 

W  Sep 7  Random Var, Expected Value 
2.1, video1 video2 

F  Sep 9  Binomial RV 
2.2, video1 v2, v3 
If necessary  videos on Big O, Big Theta: v1, v2, v3 

2  M  Sep 12  Geometric RV, conditional 
2.3, 2.4 v1,v2, v3,v4 

W  Sep 14  Variance, Markov 
3.1, 3.2 v1, v2, v3 

F  Sep 16  QuickSort QuickSelect 
2.5, v1, v2, v3, v4, v5 
HW 1 

3  M  Sep 19  Chebyshev, Coupon Collector 
3.3, v1, v2, v3, v4 

W  Sep 21  Moment Generating Functions 
4.1,4.2.1,v1 
Examples 2 & 3 on Activity 11, v2 (1235 theory, 3545 example) 

F  Sep 23  Streaming Algs, Median 
3.4 
HW 2 Activity 12a 

4  M  Sep 26  Chernoff bounds 
4.2, 4.3 v1, v2 

W  Sep 28  Graph Theory 
Diestel 1.11.3 MU 4.4,v1,v2 
Quiz 1  Pr and E[X] Reading Notes 

F  Sep 30  Hypercube Routing, viz 
4.5, v1 Reading Notes 
HW 3 Quiz 2  Rand Algs 

5  M  Oct 3  Graph Connectivity 
Diestel 1.41.7, 1.10 
HW 4: one problem due Tuesday 
W  Oct 5  Min Cut 
MU 1.4 
Quiz 3  Tail bounds  
F  Oct 7  Birthday Prob Balls into Bins Bucket Sort 
5.1, 5.2 Birthday WC MD5, v1, v2 
HW 4 Quiz 4  graphs 

6  M  Oct 10  Review Day Exam (night) 
5.3, video, video2 

W  Oct 12  Poisson 
5.4, video 
HW 5: one problem due Thursday 

F  Oct 14  Go over exam Hashing Bloom Filters 
5.5, v1, v2 
Optional: v3 Bloom tutorial 

7  M  Oct 17  Random Graphs Hamiltonians 
5.6, 5.8, v1, v2, v3 
HW 5 Applet 
W  Oct 19  Graph Coloring, BloomVideo 
Diestel 5.15.3, 10.1, v1 
Optional: D 10.210.3 LoadBal (213:00) HashProbe(3848) 

F  Oct 21  Fall break 
Optional: Bollobas I.3 

8  M  Oct 24  Streaming: Approximate Counting 
Ullman4.14.3, notes,MU8.2, vid (till 45:00)  HW 6: one problem due Tuesday. Quiz 5 
W  Oct 26 
Coloring, Random Graphs Friend/stranger 
Bollobas V.1 & V.2 & VII.1, v1, v2, v3, v4  
F  Oct 28  Ramsey Theory Quiz6: MU ch5 
Bollobas VI.1, v1, v2, v3, v4, v5, v6 
Optional: Diestel 9.1, Bollobas VI.2VI.4  
9  M  Oct 31  Streaming: Distinct Elts 
notes, notes, Ullman 4.44.6 v1 (till 41:00) 
HW 6: due Tuesday Optional: Ullman 10.1 
W  Nov 2  Cuckoo Hash, Count Min Sketch 
Handout, v1 (38:3058:00), notes 
HW 7: one problem due Thursday Optional: Ullman 7.6 

F  Nov 4  Probabilistic Method, max cut  Diestel 11.1 MU 6.1, 6.2 v1, v2. 
Quiz 7: graphs, streams Optional: Graph th'y vid (21:0036:00) 

10  M  Nov 7  Derandomizat ion, max sat  6.3, SATvid, derand cut 
HW 7: due Tuesday 
W  Nov 9  Sample & Modify graph threshold 
6.46.5 v1 (1052:00) 
HW 8: one problem due Thursday  
F  Nov 11  Second moment method, almost all graphs 
Diestel 11.211.4, v1 
Quiz 8 & 9: Hashing Optional: Bollobas VII.2VII.5 

11  M  Nov 14  Lovasz Local Lemma, edge disjoint paths 
6.6, 6.7 vid (013:00, 43:0054:00) 
HW 8: due Tuesday Quiz 10: MU 6.16.3 
W  Nov 16  Review Day Primality Test 
6.8, handout vid (till 8:00) 
vidLLL, vidLLLGeneral (till 15:00) 

F  Nov 18  RSA, AKS, MillerRabin, Riemann Hyp  6.9, v1, v2: MillerRabin 
Final Project Proposal Quiz 11: MU ch6 Optional vid 

12  M  Nov 21  Thanksgiving break 

W  Nov 23  Thanksgiving break 

F  Nov 25  Thanksgiving break 

13  M  Nov 28  Markov Chains, SAT 
7.1, 3SATvid, RWvid  Optional: exampleVid 
W  Nov 30  Recurrent vs. Transient, Gambler's Ruin 
7.2, 3SAT, DefnVid, Defn2 
Exam 2 on Thursday night (December 1) 

F  Dec 2  Random Walks on Graphs, Polya's Theorem  7.4, vid till 13, Ullman 5.1,5.3 
HW 9: one problem due Sunday Optional: Bol IX.1IX.3 

14  M  Dec 5  Parrondo's Paradox 
7.5, vid (esp. 23:0038:00) 

W  Dec 7  Stationary Distributions 
7.3,vid,vid2,  HW 9: due Thursday  
F  Dec 9 
Game Theory, minimax 
Handout  Quiz 12: MU ch7 HW 10: one problem due Sunday 

15  M  Dec 12  Final project presentations 
Eigenvectors  Optional: Ullman8.18.3 HW 10: due Tuesday 
W  Dec 14  Final project presentations 
SVD Example  
F  Dec 16  Streaming SVD, PCA, Dimension Reduction, Randomized Data Structures  Handout, Ullman 9.4, 11.111.3, skipList, treap 
Final Paper due Wednesday, Dec 21 Optional: Ullman 11.4 