CS 5330 - Randomized Algorithms

(Spring 2019)

NUS School of Computing

Prof. Seth Gilbert

Tuesday 6:30pm - 9:30pm




March 8 Review material for midterm posted.
February 21 Experimental algorithms problem set posted.
February 14 Problem set 4 posted! Project proposal submission link posted here.
January 31 Problem set 3 posted! Problem set 1 solutions posted.
January 23 Problem set 2 posted!
January 15 Problem set 1 posted!
January 15 First class! Welcome to CS5330!

Course Overview


The module will cover basic concepts in the design and analysis of randomized algorithms. It will cover both basic techniques, such as Chernoff bounds, random walks, and the probabilistic method, and a variety of practical algorithmic applications, such as load balancing, hash functions, and graph/network algorithms. The focus will be on utilizing randomization to develop algorithms that are more efficient and/or simpler than their deterministic counterparts.


There will be a variety of assignments due throughout the semester:

More details on each of these will be provided in time.


Below is the tentative schedule for the course. I will modify the schedule as the course progresses. Problem sets will be posted below on this schedule as they become available.

Class NumberDateDescription
Classical Algorithms
115/01Introduction and logistics. Karger (and Stein) MinCut. Simple branching processes.
  • Lecture notes (handwritten, pdf) [Download]
  • Problem Set 1 (due January 22) [Download]
  • Problem Set 1 solutions [Download]
  • Useful references:
    • See Mitzenmacher-Upfal Chapter 1.5.
    • Notes by Jeff Erickson: here.
    • The original paper by David Karger and Cliff Stein here.
222/01Sorting, Stable Marriage, and More!
  • Guest lecture by John Augustine.
  • 2018 Lecture notes (handwritten, pdf) [Download]
  • Problem set 1 due.
  • Problem Set 2 (due January 29) [Download]
  • Problem Set 2 solutions [Download]
  • Useful references:
    • See Mitzenmacher-Upfal Chapter 2.1 and 2.3 for linearity of expectation, conditional expectation.
    • See Mitzenmacher-Upfal Chapter 2.4 for the coupon collector (and geometric random variables).
    • See Mitzenmacher-Upfal Chapter 3.1 for Markov's Inequality.
    • Notes by Jeff Erickson on treaps: here.
329/01Hashing: Chaining, Linear Probing, and Cuckoo!
  • Lecture notes (handwritten, pdf) [Download]
  • Problem Set 3 (due February 12) [Download]
  • Problem Set 3 solutions [Download]
  • Useful references:
    • See Mitzenmacher-Upfal Chapter 2.4 for the coupon collector (and geometric random variables).
    • See Mitzenmacher-Upfal Chapter 3.3 for Chebychev's Inequality.
    • See Mitzenmacher-Upfal Chapter 5.2 for Balls-and-Bins analysis.
    • See Mitzenmacher-Upfal Chapter 5.5 for hashing.
    • Original paper on the analyzing linear probing with limited independence here.
    • Lecture notes on linear probing here.
    • Simple analysis of cuckoo hashing: here.
    • Original paper on cuckoo hashing here.
    • One way to improve cuckoo hashing: use a stash! See here.
    • A paper which argues that you should use Tabulation Hashing to build your Cuckoo hash tables here.
    • An old survey which summarize some interesting questions related to Cuckoo hashing (many of which have been solved) here.
    • A blogpost with a neat sketch of a proof that Cuckoo hashing works here.
405/02Chinese New Year!
Sampling, Markov Chains, and Random Walks.
512/02Chernoff Bounds and Sampling
  • Example applications: coin flipping, polling / sampling, load balancing, bipartite graph color balancing, and the diameter of a random graph.
  • Lecture notes (handwritten, pdf) [Download]
  • Final project topics here.
  • Proposal proposal submission: here.
  • Problem Set 4 (due February 19) [Download]
  • Problem Set 4 solutions [Download]
  • Useful references:
    • See Mitzenmacher-Upfal Chapter 4 for Chernoff Bounds.
    • See Mitzenmacher-Upfal Chapter 5.5 for hashing examples of Chernoff Bounds.
    • Jeff Erickson has some notes on Chernoff Bounds using the depth of a treap as an example.
    • One of the original early papers to study the diameter of random (regular) graphs was by Bollobas and de la Vega. (Note this is a different approach then we saw in class.)
    • This was a famous paper on randomized rumor spreading, which is very closely related to the analysis on the diameter of a random graph that we saw.
619/02Chernoff Bounds and Sampling (Part 2)
  • Randomized Rounding (for Set Cover), Flajolet-Martin approximate counter.
  • Flajolet-Martin Lecture notes (handwritten, pdf): [Download]
  • Randomized Rounding Lecture notes (handwritten, pdf):[Download]
  • Experimental Algorithms Problem Set (due March 8) [Download]
  • Useful references:
    • See Mitzenmacher-Upfal Chapter 4 for Chernoff Bounds.
    • See Mitzenmacher-Upfal Chapter 5.5 for random graph examples of Chernoff Bounds.
    • See Mitzenmacher-Upfal Chapter 17.1 for Power of Two Choices.
    • See here for Jelani Nelson's notes on Flajolet-Martin, including how to implement it using k-independent hash functions.
Break26/02No class: Mid-semester break
75/3Random Walks (Part 1)
  • Lecture notes (handwritten, pdf) [Download]
  • Analyzing random walks on a line [Link]
812/3Midterm Exam
919/3Random Walks (Part 2)
  • Lecture notes (handwritten, pdf) [Download]
  • Useful references:
    • Semester of lecture notes from Berkeley on Markov Chains here. See lectures 5-7 for details about coupling arguments.
    • You can find more detailed proofs on coupling and the Fundamental Theorem of Markov Chains here.
    • You can find details on another coupling technique (path coupling) here.
1026/3Random Walks (Part 3)
  • Lecture notes (handwritten, pdf) [Download]
  • Useful references:
    • Details on using a Doob Martingale to analyze geometric TSP here.
    • You can find more examples of Doob Martingales in Lecture 19 and Lecture 20. They give bounds on coloring random graphs, and at the same time, on the size of the largest independent set and largest clique in a random graph.
    • These notes show how to use Azuma's Inequality to get a really sharp concentration bound on the running time of QuickSort.
    • How to choose a random coloring [Link]
    • A class on Spectral Graph Theory. See here, for example, for notes on random walks and the second eigenvalue.
Advanced Topics
112/4Expert Learning
129/4Probabilistic Method
1316/4Project Presentations
End of class

Course Logistics

Office Hours

For now, office hours are by appointment. Once the semester begins, I'll schedule regular weekly office hours (and update the website here).


To ask me small logistical questions, I prefer that you grab my attention immediately before or after class. For substantive content questions, schedule a meeting with me.


This class will be loosely based on material from the book Probability and Computing by Mitzenmacher and Upfal.
This book is highly recommended. (In the past, I have used the first edition; the second edition has been recently released.)

Problem Sets

There will be weekly problem sets throughout the class. These problems sets will focus on algorithm questions: solving problems, devising algorithms, proving theorems. There will be one assignment that focuses on a larger experimental evaluation of a collection of randomized algorithms.

Problems will be graded on a simplistic 0/1/2 scale: a 0 indicates minimal understanding (or a problem not completed); a 1 indicates some understanding but many mistakes or poor presentation; 2 indicates a mostly correct answer. (Bonus points may be awarded for particularly nice solutions and/or for optional problems.)

The following rules will help keep the problem set submission and grading process running smoothly:

Some advice on problem sets:


There will be one midterm exam in the course. There is no final exam.

Academic Integrity

I take academic integrity seriously. To repeat the problem set instructions from above: the solutions you submit must be your own unique work. Any cases of cheating will be dealt with harshly: a first offense will result in at least a one letter grade deduction for the module (or potentially a zero for the entire module, depending on the severity). When in doubt, ask me what is allowed.