RANDOMIZED METHODS IN COMPUTER SCIENCE

The concept of randomness is an essential part of modern algorithm design. Informally, randomness amounts to choosing one out of a predefined set of options by flipping a coin. In this course, we will show how randomness is present in algorithms research in two different ways: (1) in the design of the algorithms themselves, and (2) in their analyses. The first amounts to allowing the algorithm to probabilistically choose between multiple options during its execution. Here, we show via classical examples how such power can lead to a better performance with respect to making exclusively deterministic choices. The second aspect deals with analysing algorithms on inputs that are subject to randomness, i.e., inputs that follow a certain distribution. Here, we will see how to give rigorous statements regarding an algorithm's behaviour on such inputs, i.e., we will give probabilistic guarantees (e.g., guarantees that hold in expectation or with high probability). In turn, this will help us better understand the complexity of the problems that these algorithms are solving.

At the end of the course, the student will be able to:
1) understand the classical approaches of incorporating randomness in algorithm design,
2) perform probabilistic analyses of algorithms in non-deterministic settings.

basic knowledge about:
- algorithms and data structures
- probability theory

Revision of Basics in Probability Theory,
Coupon Collector and Contention Resolution,
Yao's Principle and the Secretary Problem,
The Probabilistic Method,
Some Classical Randomized Algorithms: Min-Cut, Polynomial Identity Testing, and Quicksort,
Chernoff Bounds and Load Balancing,
Random Graphs,
Smoothed Analysis

Mitzenmacher, Michael, and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017.

Successful completion of the four exercise sheets that will be handed out during the course of the lectures.

Frontal instruction, black board.

English

written