CPS 630: Randomized Algorithms

Instructor: Kamesh Munagala 
   Spring Semester, 2013

Randomization is a key technique used in a variety of computational settings - in fact, its use is so ubiquitous that it is hard to be a computer scientist without appreciating the power of randomness.  Randomization not only has practical applications, but also leads to mathematically elegant proofs. This course will cover a bit of both aspects. We will try to be comprehensive in presenting basic techniques, and will illustrate each technique with some practically motivated examples. These techniques will include linearity of expectation, concentration of measure and martingales, Markov chains and mixing times, distributed algorithms, and online algorithms.

There are many additional applications that I will be unable to cover; you will be required to read and summarize one such application as part of the course project.

CPS 330 or equivalent is a HARD prerequisite.  If you have never studied algorithms before, you have to take CPS 330 instead of this course.
Discussions will be conducted via Piazza. Please post questions/doubts/comments there, and answer questions posted by your classmates.
Assignments and grades are posted via Sakai.

Tue/Thu 1:25-2:40           (D106 LSRC)        
Office Hours:       
(Kamesh) Thu  3-5pm      (D205 LSRC)
(Salman)  Wed 11-12am   (N303A North)

Grading: Homeworks (25%), Paper reading/Course project (25%; see below), MidTerm (25%), Final Exam (25%).  

Course Textbooks: 
[MR]      Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan.    (required)
[DP]      Concentration of measure for the analysis of randomized algorithms by D. Dubhashi and A. Panconesi.
[MU]     Probability and Computing by Michael Mitzenmacher and Eli Upfal

Some nice slides for the material in the [MU] book.
Randomized Algorithms course at CMU
Lecture notes by J. Aspnes (Yale)

Lecture  Date  Topics  Reading List Self-Study


Jan. 10
Part 1: The Beauty of Randomization
Introduction to random variables
Linearity of Expectation and Max 3-SAT

MR 1.0
MU 2.1-2.5, 1.4
Slides (K. Wayne)
MR 1.0
MU 2.5
2 Jan. 15
Randomized Complexity Classes
MR 1.5
Notes (L. Trevisan)

Jan 17
Karger's global mincut algorithm
Improved MinCut algorithm by recursion

Jan 22
Polynomial identity checking
Testing Bipartite perfect matchings
MR 7.1, 7.4
Notes (A. Saberi)

Jan. 24
Fingerprinting and Hashing
MR 7.1, 7.4

Jan. 29
Isolation Lemma
Perfect matchings via Gaussian elimination
Notes (A. Saberi)
MR 12.4


Jan. 31
Part 2: Concentration of Measure
Markov and Chebychev Inequalities
Randomized Median Finding
MR 3.1-3.3
MU 3.1-3.4
Coupon Collectors
MR 3.6
Feb. 5
Chernoff Bounds: Derivation and simplification
Applications to discrepancy minimization
MR 4.1, MU 4.2

Feb. 7
Sampling and Estimation Techniques
Median of means, Importance sampling
Approximate counting of combinatorial objects

MR 11.1, 11.2

Feb. 12
Oblivious Routing MR 4.2, MU 4.5.1 Lovasz Local Lemma (MR 5.5)
Notes (A. Srinivasan)
Feb. 14
Randomized rounding and congestion MR 4.3

Feb. 19
Goemans-Williamson MaxCUT algorithm

Feb. 21
Locality Sensitive Hashing SimHash paper


Feb. 26
Tail bounds for occupancy problems
Power of two choices
MR 3.1, 3.6, 4.4.4
Notes (A. Gupta)
Presentation (B. Vocking)
Cuckoo Hashing (Notes)
Feb. 28
Martingales: Stopping theorem, Wald's identity
Application to Actuarial Science: Lundberg's inequality
MR 4.4
MU 12.1-12.3

Mar. 5
Azuma-Hoeffding inequality
Balls and Bins; Chromatic number
MU 12, MR 4.4


Mar. 7
Average case analysis:
Euclidean TSP and Karp's Heuristic
Tour lengths in Euclidean TSP
Notes (A. Gupta)


Mar. 19
Part 3: Markov Chains and Monte Carlo
Randomized algorithm for 3-SAT
MU 7

Mar. 21
Stationary distributions
Random walks on graphs
MU 7

Mar. 26
M/M/1 queue
Metropolis algorithm
MU 8.6
MU 10.4

Mar. 28
Coupling and Mixing times
Uniform sampling of independent sets
MU 11

Apr. 2
<< SLACK >>

Apr. 4
Part 4: Miscellaneous
Luby's maximal independent set algorithm
MR 12.3
How it's done in nature
24 Apr. 9
Weighted majority algorithm Notes

Apr. 11
Yao's min-max principle and lower bounds
Zero-sum games

26 Apr. 16
Take Home FINAL

Paper Reading: I will unfortunately have to skip many interesting topics. However, you will be required to read one or more papers on such a topic, and summarize the ideas in your own words in a few pages. Here are some suggested topics and papers (please let me know if you need more suggestions):
  1. E. J. Candès. The restricted isometry property and its implications for compressed sensing. Compte Rendus de l'Academie des Sciences, Paris, Serie I, 346 589-592.
  2. N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the frequency moments, JCSS 58 (1): 137–147, 1999.
  3. Practical Hashing Schemes
  4. Linear program rounding:
  5. Random graphs and power laws:
  6. Fan Chung. Four proofs for the Cheeger inequality and graph partition algorithms ICCM 2007
  7. Dan Spielman. Expander graphs, Error correcting codes, and Expander codes (course notes)
  8. Smoothed analysis or "Why is knapsack easy in practice"?
  9. SAT Solvers and Thresholds, or "Why is SAT easy in practice"?