Randomized Algorithms Analysis and Design

Catalog description

This course explores applications of probabilistic techniques to computer science. The main focus is how to leverage randomness in algorithms and how to perform probabilistic analysis of algorithms. Randomized algorithms are often faster and simpler than their deterministic counterparts, with the weaker assertion that correctness is not always guaranteed. Coverage includes analyzing algorithms via proofs and programming assignments to implement algorithms and sampling techniques. Topics include probabilistic method, balls and bins, random graphs, random walks, discrete time Markov chains, the Monte Carlo method, and examples of applications in many areas of computer science.