Notes on Randomized Algorithms

These are notes for the Yale course CPSC 469/569 Randomized Algorithms. This document also incorporates the lecture schedule and assignments, as well as some sample assignments from previous semesters. Because this is a work in progress, it will be updated frequently over the course of the semester. 

Much of the structure of the course follows Mitzenmacher and Upfals's Probability and Computing: Randomized Algorithms and Probabilistic Analysis [MU05], with some material from Motwani and Raghavan's Randomized Algorithms [MR95]. In most cases you'll find these textbooks contain much more detail than what is presented here, so it is probably better to consider this document a supplement to them than to treat it as your primary source of information. 

The most recent version of these notes will be available at http://www.cs.yale.edu/homes/aspnes/classes/469/notes.pdf. More stable archival versions may be found at https://arxiv.org/abs/2003.01902. 

I would like to thank my many students and teaching fellows over the years for their help in pointing out errors and omissions in earlier drafts of these notes.