Lec.  Date  Syllabus  Reading  Handouts/Homework


1 
Tu, Jan 21 
Introduction. Verifying polynomial identities.
For discussion: Review of conditional probability, Bayes' law, the law of total probability. 
Chapters 1.11.3 
General Course Information,
Collaboration and Honesty Policy,
HW1 out 
2 
Th, Jan 23 
Verifying matrix multiplication. 
Chapters 1.21.4 
Friday: HW1 due, HW2 out 
3 
Tu, Jan 28 
Bayesian view on amplification. Randomized Min Cut. Random variables.
For discussion: Random variables. Expectation. 
Chapters 1.41.5 

4 
Th, Jan 30 
Bernoulli and Binomial Random Variables. Jensen's inequality. Conditional expectation. 
Chapters 2.12.3 
Friday: HW2 due, HW3 out 
5 
Tu, Feb 4 
Conditional Expectation. Geometric distribution. Coupon Collector Problem.
Slides with notes.

Chapters 2.32.5 

6 
Th, Feb 6 
Expected run time of Quicksort. Markov's inequality. Variance.
Slides with notes. 
Chapters 2.5, 3.13.2 
Friday: HW3 due, HW4 out 
7 
Tu, Feb 11 
Variance. Chebyshev's inequality.
Slides with notes. 
Chapters 3.23.3 

8 
Th, Feb 13 
Median and Mean. Computing the median of an array. 
Chapters 3.43.5 
Friday: HW4 due, HW5 out 

Tu, Feb 18 
Monday Schedule 
9 
Th, Feb 20 
Chernoff and Hoeffding Bounds.
Slides with notes. 
Chapters 4.14.2 
Friday: HW5 due, HW6 out 
10 
Tu, Feb 25 
Applications of Chernoff and Hoeffding Bounds.
Slides with notes. 
Chapters 4.34.5 

11 
Th, Feb 27 
Routing on the Hypercube 
Chapter 4.6 
Friday: HW6 due, HW7 out 
12 
Tu, Mar 3 
Finish Permutation Routing on Hypercube. Birthday Paradox, balls and bins model 
Chapters 5.15.2 

13 
Th, Mar 5 
Poisson distribution, Poisson approximation
Slides with notes. 
Chapters 5.35.4 
Friday: HW7 due, practice midterm problems out 

Mar 715 
Spring Recess, subsequent classes are online until further notice 
14 
Tu, Mar 17 
Poisson approximation
Slides with notes. 
Chapter 5.4 

15 
Th, Mar 19 
Hashing
Slides with notes. 
Chapters 5.5, 15.315.3.1 
Friday: HW8 out 

postponed 
Midterm Exam 


16 
Tu, Mar 24 
Universal hashing, perfect hashing, bloom filters
Slides with notes. 
Chapters 5.5, 15.3 

17 
Th, Mar 26 
Random graphs. Finding Hamiltonian cycles in random graphs.
Slides with notes. 
Chapter 5.6 
Friday: hw8 due, HW9 out 
18 
Tu, Mar 31 
Finding Hamiltonian cycles in random graphs (continued)
Slides with notes. 
Chapter 5.6 

19 
Th, Apr 2 
Probabilistic method. Derandomization: conditional expectations
Slides with notes. 
Chapters 6.16.3 
Friday: hw9 due, HW10 out 
20 
Tu, Apr 7 
Sample and modify. The second moment method.
Slides with notes. 
Chapters 6.46.5 

21 
Th, Apr 9 
The second moment method. Conditional expectation inequality. Lovasz Local Lemma
Slides with notes. 
Chapters 6.56.6 
Friday: hw10 due, HW11 out 
22 
Tu, Apr 14 
Lovasz Local Lemma and algorithmic Lovasz Local Lemma
Slides with notes. 
Chapters 6.76.10 

23 
Th, Apr 16 
Algorithmic Lovasz Local Lemma. Applications of LLL.
Slides with notes. 
Chapters 6.76.10 
Friday: HW11 due, HW12 out 
24 
Tu, Apr 21 
Markov chains. Drunkard's walk. Randomized algorithm for 2SAT.
Slides with notes. 
Chapters 7.1 


W, Apr 22 
Monday Schedule: No Discussion Sections 
25 
Th, Apr 23 
Randomized algorithm for 3SAT. Gambler's Ruin. Classification of Markov chains. Stationary distributions.
Slides with notes. 
Chapters 7.17.3 
Friday: HW12 due 
26 
Tu, Apr 28 
Stationary distributions. Random walks on graphs
Slides with notes. 
Chapters 7.37.4 

27 
Th, Apr 30 
Sneak peek into sublinear algorithms and differential privacy 



M, May 4  W, May 6 
Final Exam: released at 2pm on Monday on piazza, due at 2pm on Wednesday on Gradescope 