CS 537: Randomness in Computing
Fall 2024

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 12:30pm-1:30pm, Th 3pm-4pm CDS 1028
TF Ephraim Linder Wed TBA TBA

Syllabus, Lecture Slides, Reading

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

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

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