The powerful role played by randomness in computation has been
among the central discoveries in the foundations of computer
science over the last three decades. Randomized algorithms are
algorithms that make random choices as they proceed, and have
had a fundamental impact on several areas of computer science
(e.g., distributed algorithms, cryptography, resource allocation,
approximation algorithms). This course is an introduction to
randomized algorithms. It aims to teach rigorous methods to
design and analyze such algorithms, and to present some of
the key applications of randomization in diverse fields of
computer science such as distributed computing, resource allocation,
scheduling, and packet routing.