Event

Randomized algorithms and data structures rely on random experiments. While the design of deterministic algorithms is often driven by a pessimistic view of worst-case behavior, randomized algorithms employ approaches that occasionally fail but perform much better most of the time.

The running time of such algorithms, as well as the solution quality (in the case of optimization problems) and sometimes correctness (in the case of computation problems), are subject to randomness. Therefore, a formal analysis focuses on expected values and success probabilities. We will explore both classical examples and current research topics in the areas of hashing and graph theory. Specialised design methods (such as probability amplification) and advanced analysis tools from probability theory (such as coupling, Poissonization, and concentration bounds) will be applied. We will often see that randomized approaches are more efficient or simpler than all (or at least all known) deterministic approaches.

We will briefly address, on the theory side, how randomized complexity classes relate to well-known classes such as P and NP and, on the the practical side, how to implement randomized algorithms on common (essentially deterministic) computers using pseudo-randomness.

Competence Goals:

Students will be able to:
- understand when and why randomization is useful or necessary to solve an algorithmic problem,

- explain central design methods and analysis tools in the context of randomized algorithms,

- design and explain simple randomized algorithms and data structures to solve a given problem,

- determine which tools are suitable for analyzing a given randomized algorithm or data structure, and apply them.