Algorithms & Complexity

Randomized Algorithms and Probabilistic Analysis of Algorithms

Advanced Course, 2+1

Basic Information

Lectures:Wednesdays, 1400-1600, E 1 4, Room 023
Lecturers:Philip Wellnitz
First lecture:TBD
Assistant:Baris Can Esmer
First tutorial:TBD
Prerequisites:Basic knowledge in algorithms and stochastics


Randomization is a helpful tool when designing algorithms. When there are many possible options many of which are good, it is a lot easier to have the algorithm flip a coin rather than describing an appropriate deterministic rule. Also, worst-case effects might be avoided this way. For these reasons, many practical algorithms use randomization, such as for example primality testing in cryptography. In other case, the input to an algorithm itself can already be assumed to be probabilistic. For example, sorting algorithms often have a bad worst-case running time only due to a single instance, which is very unlikely to occur in a real input. In these cases it make sense to analyze algorithms under probabilistic input models.

In this course, we will introduce you to the foundations of randomized algorithms and probabilistic analysis of algorithms. We will cover different combinatorial settings such as load balancing, sorting, and network and graph problems.


DateTopicMaterialReference (see below)ExerciseDue
October 26Introduction, Course Overview    
(November 2)     
November 9     
November 16     
November 23     
November 30     
December 7     
December 14     
December 21     
January 4     
January 11     
January 18     
January 25     
February 1     
February 8