CS 5330 - Randomized Algorithms

(Spring 2019)

NUS School of Computing

Prof. Seth Gilbert

Tuesday 6:30pm - 9:30pm

I3-0344

      

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 Mitzenmacher-Upfal 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 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.
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 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.
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 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.
6	19/02	Chernoff 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.
Break	26/02	No class: Mid-semester 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 First half review (pdf) [Download] 2018 Midterm [Download] 2018 Midterm Solution Sketches [Download] 2019 Midterm [Download] 2019 Midterm Solution Sketches [Download]
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 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.
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:

• You must hand in a solution that is unique, consisting of your work alone. You may discuss high-level strategy with other students in the class. You may read the textbook, or other reference pages on general topics. However, the solution you hand in must be written by you alone, and any similarities to any other student's submission (or to any web page or solution on the web) will be considered cheating. It will be considered equally cheating whether you copy from someone else, or if someone else copies from you.

  Do not compare or share your solution with others.

• You may not read or use solutions found on the web for identical problems, whether from prior years of this class or from other classes elsewhere.
• You may talk to people about general strategies, and you may use reference material available on the web (e.g., Wikipedia, lecture notes from other classes, etc.). If you talk to anyone else or read any reference material, you may not take notes on your discussion. Afterwards, spend half an hour on facebook (or some equivalent activity), before working further on the problem set.
• You are encouraged to typeset your problem sets (and are especially encouraged to use Latex). However, you may submit your problem sets in any form that is clear and easily legible. You are also encouraged to include many pictures and diagrams and examples in your problem sets. It is perfectly acceptable to typeset the problem set and attach hand-drawn figures.
• Problem sets should be handed in no later than the beginning of class on the day they are due. You may bring a physical copy of the problem set to class to give to me before the lecture begins, or you may submit it electronically on IVLE.
• Problem sets not handed in by the beginning of lecture will be considered late, and 10% of the points deducted. Problem sets not handed until the day after the deadline will have an additional 10% deducted (leave late problem sets in the envelope by my door). Beyond this point, problem sets will not be accepted.

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 type-set, 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.