CS 761 - Randomized Algorithms - Fall 2019

Course Description

Randomness is a very powerful technique in algorithm design. We will discuss tools and methods for harnessing the power of randomization in the design and analysis of algorithms and stochastic processes. Prerequisites include basic knowledge of probability, and mathematical maturity.

Logistics

Lecture: Fridays, 10:00 AM - 12:50 PM, DC 2585
Instructor: Gautam Kamath
Teaching Assistant: Vedat Levi Alev
Office Hours: Fridays, 12:50 PM - 2:00 PM, DC 3124

Lecture Schedule

Lectures from this course will be scribed by students.

Lecture 1 (September 6): Probability basics, Randomized Quicksort, Markov's Inequality, Coupon Collectors (scribe notes)
Lecture 2 (September 13): Chebyshev's Inequality, Chernoff Bound, Minimum Cut, Minimum Spanning Tree (scribe notes)
Lecture 3 (September 20): Balls and Bins, Hashing, Bloom Filters (scribe notes)
Lecture 4 (September 27): k-wise Independence, Universal Hash Functions, Perfect Hashing, Heavy Hitters, Distinct Elements (scribe notes)
Lecture 5 (October 4): Streaming and Sketching Frequency Moments, Dimensionality Reduction (scribe notes)
Lecture 6 (October 11): Probabilistic Methods, Lovasz Local Lemma (scribe notes)
Lecture 7 (October 25): Random Walks, Markov Chains (scribe notes)
Lecture 8 (November 1): Coupling, Mixing Time, Monte Carlo (scribe notes)
Lecture 9 (November 8): Monte Carlo, Randomized Rounding, Max Cut, Derandomization, Sparsification
Lecture 10 (November 15): Spectral Sparsification, Algebraic Methods (scribe notes)
Lecture 11 (November 22): Property Testing (scribe notes)
Lecture 12 (November 29): Data Privacy (scribe notes)

Assignments

All assignments are to be submitted by email to the instructor and teaching assistant before the deadline.

Late Policy: You have a total of three 24 hour, no-questions-asked, extensions in this class. You may use any number of these for each of the three problem sets. The purpose of this policy is so that I don't introduce bias or unfairness in granting people extensions.

Problem Set 1: Assigned September 22, due October 7.
Problem Set 2: Assigned October 13, due November 3.
Problem Set 3: Assigned November 10, Due November 22.
Project: Proposal due November 8, report due December 22.

Books and References

No textbook is required for this course, though we will generally cover various topics from the book below by Motwani and Raghavan. The following books are classic references in this area.

"Randomized Algorithms," by Rajeev Motwani and Prabhakar Raghavan.
"Probability and Computing: Randomized Algorithms and Probabilistic Analysis," by Michael Mitzenmacher and Eli Upfal.
"The Probabilistic Method," by Noga Alon and Joel Spencer.

Lap Chi Lau's lecture notes are also a good resource, as the lectures are heavily based off them.

Grading

There will scribe notes (10%), 3 homework assignments (55%), and a final project (35%).

For scribe notes, please use the LaTeX template here.