CS 537: Randomness in Computing
Spring 2020

Course Overview

This course covers the design and analysis of randomized algorithms and, more generally, applications of randomness in computing. Randomness is used in designing efficient algorithms and has numerous applications in learning, cryptography, distributed systems, networking, data mining, data privacy, complexity theory and other areas of computer science. You will learn fundamental tools from probability and see many applications of randomness in computing. Randomness in computing picture

Course Staff

Office Hours Office
Prof. Sofya Raskhodnikova Tu 1-2pm,Th 4-5pm MCS 112
TF Gavin Brown M 3:15-4:15pm, W 2:30-3:30pm EMA 302

Syllabus, Lecture Slides, Reading

Warning: Most of the material in lectures is covered on the blackboard.

1 Tu, Jan 21 Introduction. Verifying polynomial identities.
For discussion: Review of conditional probability, Bayes' law, the law of total probability.
Chapters 1.1-1.3 General Course Information, Collaboration and Honesty Policy, HW1 out
2 Th, Jan 23 Verifying matrix multiplication. Chapters 1.2-1.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.4-1.5
4 Th, Jan 30 Bernoulli and Binomial Random Variables. Jensen's inequality. Conditional expectation. Chapters 2.1-2.3 Friday: HW2 due, HW3 out
5 Tu, Feb 4 Conditional Expectation. Geometric distribution. Coupon Collector Problem.
Slides with notes.
Chapters 2.3-2.5
6 Th, Feb 6 Expected run time of Quicksort. Markov's inequality. Variance.
Slides with notes.
Chapters 2.5, 3.1-3.2 Friday: HW3 due, HW4 out
7 Tu, Feb 11 Variance. Chebyshev's inequality.
Slides with notes.
Chapters 3.2-3.3
8 Th, Feb 13 Median and Mean. Computing the median of an array. Chapters 3.4-3.5 Friday: HW4 due, HW5 out
Tu, Feb 18 Monday Schedule
9 Th, Feb 20 Chernoff and Hoeffding Bounds.
Slides with notes.
Chapters 4.1-4.2 Friday: HW5 due, HW6 out
10 Tu, Feb 25 Applications of Chernoff and Hoeffding Bounds.
Slides with notes.
Chapters 4.3-4.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.1-5.2
13 Th, Mar 5 Poisson distribution, Poisson approximation
Slides with notes.
Chapters 5.3-5.4 Friday: HW7 due, practice midterm problems out
Mar 7-15 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.3-15.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.1-6.3 Friday: hw9 due, HW10 out
20 Tu, Apr 7 Sample and modify. The second moment method.
Slides with notes.
Chapters 6.4-6.5
21 Th, Apr 9 The second moment method. Conditional expectation inequality. Lovasz Local Lemma
Slides with notes.
Chapters 6.5-6.6 Friday: hw10 due, HW11 out
22 Tu, Apr 14 Lovasz Local Lemma and algorithmic Lovasz Local Lemma
Slides with notes.
Chapters 6.7-6.10
23 Th, Apr 16 Algorithmic Lovasz Local Lemma. Applications of LLL.
Slides with notes.
Chapters 6.7-6.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.1-7.3 Friday: HW12 due
26 Tu, Apr 28 Stationary distributions. Random walks on graphs
Slides with notes.
Chapters 7.3-7.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


Sample nameplate
Change the name to yours in this PPTX file, print it, and bring to class.
Information for graders: PDF
LaTeX resources
TexShop is a latex editor for the Mac platform; TexNiCenter is a tex editor for Windows; ShareLatex is a web-based latex system (allows you to avoid latex installation on your machine).
Not so short intro to latex; a latex tutorial.
Homework template files: tex, pdf, cls, jpg.

Sofya Raskhodnikova