Randomized Algorithms and Probabilistic Analysis of Algorithms

Advanced Course, 2+1

Basic Information

Lectures:Monday, 16:15 - 18:00, E1 4 024
Lecturers:Thomas Kesselheim and Kurt Mehlhorn
First lecture:April 25, 2015
Tutorials:Wednesday, 10:00 - 12:00, E 1 4 023, biweekly
Assistant:Pavel Kolev
First tutorial:TBA
Prerequisites:Basic knowledge in algorithms and stochastic


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.


There will be oral exams after the lecture period by individual appointment. You are required to get 50 % of the points in the exercises to take the exam.

Exercise Sets

Exercise SetDue dateTutorial Session
Exercise Set 1May 9May 11
Exercise Set 2May 30June 1
Exercise Set 3June 13June 15
Exercise Set 4June 27June 29
Exercise Set 5July 11July 13
Exercise Set 6July 25July 27

E-Mail Announcements

To sign up for the announcement e-mail list, please fill out this form. You will be sent e-mail requesting confirmation.

Your name:
Your e-mail address:


  • Randomized Algorithms by Motwani/Raghavan 
  • Probability and Computing by Mitzenmacher/Upfal 
  • Chapter 13 in Algorithm Design by Kleinberg/Tardos available online (see sample chapters)