CS 537: Randomness in Computing
Spring 2018

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 Email id Office Hours
Prof. Sofya Raskhodnikova MCS 279 sofya M,W 4-5pm
Nithin M. Varma nvarma
Erasmo Tani etani

Syllabus, Lecture Slides, Reading

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

1 M, Jan 22 Introduction. Verifying polynomial identities. Chapters 1.1-1.2 General Course Information, Collaboration and Honesty Policy, HW1 out
2 W, Jan 24 Review of conditional probability, Bayes' law, the law of total probability. Chapters 1.2-1.3 On Thursday: HW1 due, HW2 out
3 M, Jan 29 Verifying matrix multiplication. Naive Bayesian classifier. Chapters 1.3-1.4
4 W, Jan 31 Randomized Min-Cut. Random variables. Chapters 1.5, 2.1 On Thursday: HW2 due, HW3 out
5 M, Feb 5 Expectation. Bernoulli and Binomial Random Variables. Chapters 2.1-2.3
6 W, Feb 7 Conditional Expectation. Geometric distribution. Coupon Collector Problem. Chapters 2.3-2.4 On Thursday: HW3 due, HW4 out
7 M, Feb 12 Expected run time of Quicksort. Markov's inequality. Variance. Chapters 2.5, 3.1-3.2
8 W, Feb 14 Variance. Chebyshev's inequality. Chapters 3.2-3.3 On Thursday: HW4 due, HW5 out
M, Feb 19 Presidents' Day Holiday
9 Tu, Feb 20 Median and Mean. Computing the median of an array. Chapters 3.4-3.5
10 W, Feb 21 Chernoff and Hoeffding Bounds. Chapters 4.1-4.2 On Thursday: HW5 due, HW6 out
11 M, Feb 26 Applications of Chernoff and Hoeffding Bounds Chapters 4.2-4.5
12 W, Feb 28 Routing on the Hypercube Chapter 4.6 On Thursday: HW6 due, HW7 out
Feb 5-9 Spring Recess
13 M, Mar 12 Birthday Paradox, balls and bins model Chapters 5.1-5.2
14 W, Mar 14 Poisson distribution, Poisson approximation Chapters 5.3-5.4 On Thursday: HW7 due, practice midterm problems out
15 M, Mar 19 Review
16 W, Mar 21 Midterm Exam On Thursday: HW8 out
17 M, Mar 26 Poisson approximation Chapters 5.4-5.5 Midterm solutions distributed
18 W, Mar 28 Poisson approximation. Hashing. Chapter 5.4-5.5 Graded midterms distributed. On Thursday: hw8 due, HW9 out
19 M, Apr 2 Bloom filters. Random graphs Chapters 5.5-5.6
20 W, Apr 4 Random graphs. Finding Hamiltonian cycles in random graphs. Chapter 5.6 On Thursday: hw9 due, HW10 out
21 M, Apr 9 Probabilistic method. Derandomization: conditional expectations Chapters 6.1-6.3
22 W, Apr 11 Sample and modify. The second moment method. Chapters 6.4-6.5 On Thursday: hw10 due, HW11 out
M, Apr 16 Patriots Day Holiday
23 W, Apr 18 The seconds moment method. Conditional expectation inequality. Chapters 6.5-6.6 On Thursday: HW11 due, HW12 out
24 M, Apr 23 Lovasz Local Lemma Chapters 6.7-6.10
25 W, Apr 25 Algorithmic Lovasz Local Lemma Chapters 6.7-6.10 On Thursday: HW12 due, HW13 out (don't hand in)
26 M, Apr 30 Markov Chains (lecture given by Nithin Varma) Chapters 7.1-7.2
27 W, May 2 Review (lecture given by Nithin Varma)
M, May 7 Final Exam: 3pm-5pm (in the same room as the lecture)


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