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.


Lecture Schedule

Lectures from this course will be scribed by students.


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.

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. Lap Chi Lau's lecture notes are also a good resource, as the lectures are heavily based off them.


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

For scribe notes, please use the LaTeX template here.