CS 537: Randomness in Computing
Spring 2026

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 T 2-3pm, Th 3-4pm CDS 1028
TF: Diptaksho PalitWed 2-4pm CDS 362 A
Grader: Mutiraj Laksanawisit ----

Syllabus, Lecture Slides, Reading

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

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

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