CS 537: Randomness in Computing
Fall 2022

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 4:30pm-5:30pm, Th 2pm-3pm MCS 112
TF Fabian Spaeh Wed 4:45pm-5:45pm, Th 4:45pm-5:45pm MCS B24

Syllabus, Lecture Slides, Reading

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

Lec.Date(Tentative) TopicsReadingHandouts/Homework
1 Tu, Sep 6 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, Sep 8 Verifying matrix multiplication. Bayesian view on amplification.
Slides with notes.		 Chapters 1.2-1.4 HW1 due, HW2 out
3 Tu, Sep 13 Randomized Min Cut. Random variables.
Slides with notes.
For discussion: Random variables.		 Chapters 1.4-1.5
4 Th, Sep 15 Random variables. Expectation. Bernoulli and Binomial Random Variables. Jensen's inequality.
Slides with notes.		 Chapters 2.1-2.3 HW2 due, HW3 out
5 Tu, Sep 20 Conditional Expectation. Branching process. Geometric distribution.
Slides with notes.		 Chapters 2.3-2.4
6 Th, Sep 22 Coupon Collector Problem. Expected run time of Quicksort.
Slides with notes.		 Chapters 2.4-2.5 HW3 due, HW4 out
7 Tu, Sep 27 Markov's inequality. Variance, covariance.
Slides with notes.		 Chapters 3.1-3.3
8 Th, Sep 29 Variance of binomial and geometric RVs. Chebyshev's inequality. Computing the median of an array.
Slides with notes.		 Chapters 3.2-3.5 HW4 due, HW5 out
9 Tu, Oct 4 Computing the median of an array.
Slides with notes.		 Chapters 3.5
10 Th, Oct 6 Chernoff and Hoeffding Bounds.
Slides with notes.		 Chapters 4.1-4.2 HW5 due, HW6 out
Tu, Oct 11 Monday Schedule
11 Th, Oct 13 Applications of Chernoff and Hoeffding Bounds. Routing on the Hypercube
Slides with notes.		 Chapters 4.3-4.5, 4.6 HW6 due, HW7 out
12 Tu, Oct 18 Finish Permutation Routing on Hypercube. Birthday Paradox, balls and bins model
Slides with notes.		 Chapters 4.6,5.1-5.2
13 Th, Oct 20 Poisson distribution, Poisson approximation
Slides with notes.		 Chapters 5.3-5.4 HW7 due, practice midterm problems out
14 Tu, Oct 26 Review
15 Th, Oct 27 Midterm Exam in EPC 209 HW8 out
16 Tu, Nov 1 Review Poisson distribution, Poisson approximation, random graphs
Taught by Fabian Spaeh		 Chapters 5.3-5.4; 5.6
17 Th, Nov 3 Finding Hamiltonian cycles in random graphs
Slides with notes.		 Chapter 5.6 HW8 due, HW9 out
18 Tu, Nov 8 Hashing
Slides with notes.		 5.5, 15.3-15.3.1
19 Th, Nov 10 Universal hashing, perfect hashing, bloom filters
Slides with notes.		 Chapters 5.5, 15.3 HW9 due, HW10 out
20 Tu, Nov 15 Probabilistic method. Derandomization: conditional expectations
Slides with notes.		 Chapters 6.1-6.3
21 Th, Nov 17 Sample and modify. The second moment method.
Slides with notes.		 Chapters 6.4-6.5 HW10 due, HW11 out
22 Tu, Nov 22 Conditional expectation inequality. Lovasz Local Lemma. Applications of LLL.
Slides with notes.		 Chapters 6.5-6.6
Nov 23-27 Thanksgiving Recess
23 Tu, Nov 29 Lovasz Local Lemma and algorithmic Lovasz Local Lemma
Slides with notes.		 Chapters 6.7-6.10
24 Th, Dec 1 Markov chains. Drunkard's walk. Randomized algorithm for 2SAT.
Slides with notes.		 Chapter 7.1 HW11 due, HW12 out
25 Tu, Dec 6 Randomized algorithm for 3SAT. Gambler's Ruin. Classification of Markov chains. Stationary distributions. Random walks on graphs.
Slides with notes. 		Chapters 7.1-7.3
26 Th, Dec 8 Random walks on graphs. Algorithm for s-t-connectivity. Sublinear algorithms.
Slides with notes.		 Chapters 7.3-7.4 HW12 due
Extra Sneak peek into sublinear algorithms and differential privacy
Monday, December 19 Final Exam: 12:00pm-2:00pm in CAS 216

Miscellaneous

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; Overleaf 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, jpg.
Sofya Raskhodnikova