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.

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.
Slides with notes.		 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 19Computing the median of an array. Chernoff bounds. Chapters 3.5,4.1-4.2
Tu, Feb 24Snow Day: BU was closed
10 Th, Feb 26 Chernoff and Hoeffding Bounds and their applications.
Slides with notes.		 Chapters 4.1-4.3,4.5 HW5 due, HW6 out
11 Tu, Mar 3 Applications of Chernoff and Hoeffding Bounds: set balancing, routing on the hypercube Chapters 4.4, 4.6
12 Th, Mar 5 Finish Permutation Routing on Hypercube. Birthday Paradox, balls and bins model Chapters 4.6,5.1-5.2 HW6 due, practice midterm problems out
Mar 7-15Spring Recess
13 Tu, Mar 17 Poisson distribution, Poisson approximation Chapters 5.3-5.4
14 Th, Mar 19 Midterm Exam HW7 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 Chapter 5.6 HW7 due, HW8 out
18 Tu, Mar 31 Hashing, universal hashing, perfect hashing 5.5, 15.3-15.3.1
19 Th, Apr 2 Probabilistic method. Derandomization: conditional expectations Chapters 6.1-6.3 HW8 due, HW9 out
20 Tu, Apr 7 Sample and modify. The second moment method. Chapters 6.4-6.5
21 Th, Apr 9 Conditional expectation inequality. Lovasz Local Lemma. Applications of LLL. Chapters 6.5-6.6 HW9 due, HW10 out
22 Tu, Apr 14 Lovasz Local Lemma and algorithmic Lovasz Local Lemma Chapters 6.7-6.10
23 Th, Apr 16 Markov chains. Drunkard's walk. Randomized algorithm for 2SAT. Chapter 7.1 HW10 due, HW11 out
24 Tu, Apr 21 Randomized algorithm for 3SAT. Gambler's Ruin. Classification of Markov chains. Stationary distributions. Random walks on graphs. Chapter 7.1-7.3
25 Th, Apr 23 Random walks on graphs. Algorithm for s-t-connectivity. Chapters 7.3-7.4 HW11 due, HW12 out
26 Tu, Apr 28Cover time for random walks (Matthews' Theorem). Parrondo's Paradox Chapters 7.3-7.5
27 Th, Apr 30 Sneak peek into sublinear algorithms and differential privacy HW12 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