News
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
Description
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.
Coursework
There will be a variety of assignments due throughout the semester:
 There will be (approximately) weekly problem sets covering the algorithms and techniques described in class.
 Toward the middle of the semester, there will be an experimental evaluation in which you implement and experiment with a family of randomized algorithms.
 There will be one midterm exam.
 Throughout the semester, you will work on a project exploring the power of randomization in a context of interest to you.
More details on each of these will be provided in time.
Schedule
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
Number  Date  Description 
  Classical Algorithms 
1  15/01  Introduction 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 MitzenmacherUpfal Chapter 1.5.
 Notes by Jeff Erickson: here.
 The original paper by David Karger and Cliff Stein here.

2  22/01  Sorting, 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 MitzenmacherUpfal Chapter 2.1 and 2.3 for linearity of expectation, conditional expectation.
 See MitzenmacherUpfal Chapter 2.4 for the coupon collector (and geometric random variables).
 See MitzenmacherUpfal Chapter 3.1 for Markov's Inequality.
 Notes by Jeff Erickson on treaps: here.

3  29/01  Hashing: 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 MitzenmacherUpfal Chapter 2.4 for the coupon collector (and geometric random variables).
 See MitzenmacherUpfal Chapter 3.3 for Chebychev's Inequality.
 See MitzenmacherUpfal Chapter 5.2 for BallsandBins analysis.
 See MitzenmacherUpfal 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.

4  05/02  Chinese New Year!

  Sampling, Markov Chains, and Random Walks. 
5  12/02  Chernoff 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 MitzenmacherUpfal Chapter 4 for Chernoff Bounds.
 See MitzenmacherUpfal 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.

6  19/02  Chernoff Bounds and Sampling (Part 2)
 Randomized Rounding (for Set Cover), FlajoletMartin approximate counter.
 FlajoletMartin Lecture notes (handwritten, pdf): [Download]
 Randomized Rounding Lecture notes (handwritten, pdf):[Download]
 Experimental Algorithms Problem Set (due March 8) [Download]
 Useful references:
 See MitzenmacherUpfal Chapter 4 for Chernoff Bounds.
 See MitzenmacherUpfal Chapter 5.5 for random graph examples of Chernoff Bounds.
 See MitzenmacherUpfal Chapter 17.1 for Power of Two Choices.
 See here for Jelani Nelson's notes on FlajoletMartin, including how to implement it using kindependent hash functions.

Break  26/02  No class: Midsemester break

7  5/3  Random Walks (Part 1)
 Lecture notes (handwritten, pdf) [Download]
 Analyzing random walks on a line [Link]

8  12/3  Midterm Exam

9  19/3  Random Walks (Part 2)
 Lecture notes (handwritten, pdf) [Download]
 Useful references:
 Semester of lecture notes from Berkeley on Markov Chains here. See lectures 57 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.

10  26/3  Random 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 
11  2/4  Expert Learning

12  9/4  Probabilistic Method

13  16/4  Project 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).
Contact
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.
Book
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:
 Answers to homework should be written at a level suitable for and to address the instructor. In other words, don't put in long explanation for trivial things.

You will be graded not only on the correctness and efficiency of your answers, but also on your clarity. Therefore, it pays to make your answers more concise and clearer. Understandability of the solution is as desirable as correctness. Sloppy answers will be at a disadvantage. Learn to make appropriate definitions to make your answers more precise and concise.

Solutions do not have to be typeset, but they have to be neat and readable. Do not waste your time beautifying your answers. If you want to spend more time, you should spend it on improving its clarity, understandability, and other aspects of its technical content.

From a previous module, you can find some advice on proofs here.

From a previous module, you can find a sample of what a good solution looks like here.
Exams
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.