Randomized Algorithms

§ Overview

Notes from Dr. Samson Zhou's CSCE 658 — Randomized Algorithms course.

Randomized algorithms over a traditional setting such as polynomial identity testing and Karger's min cut, and in the streaming model such as Count-Sketch and Morris' counter.,Other covered topics are concentration inequalities (Chebyshev, Chernov), dimensionality reduction (Johnson-Lindenstrauss), heavy-hitters, clustering, coresets, Lovasz local lemma, linear programming, differential privacy.

§ Motivation

We motivate the usefulness of randomized algorithms by inspecting the following problems and seeing how such algorithms are able to arrive at a solution that is very close to, if not the, correct answer with high probability.