Department of Computer Science | Institute of Theoretical Computer Science

CADMO - Center for Algorithms, Discrete Mathematics and Optimization

Randomized Algorithms and Probabilistic Methods


Prof. Dr. Angelika Steger


Frederik Benzing , Marcelo Matheus Gauy , Charlotte Knierim and Ulysse Schaller

Time and Place

Lecture: Tuesday 13:15 - 14:00 in CAB G 51 and Thursday 08:15 - 10:00 in CAB G 51

ATTENTION: The first lecture (18.09) will be held on HG E1.1

Exercise Class: Tuesday, 16:15 - 18:00 in CAB G 51

Exam: Saturday, 15.12, 10:00 - 13:00 in HG F1


Students of Computer Science or Mathematics in the 5th semester or later. Knowledge of topics covered in the lecture "Algorithms, Probability, and Computing" is not required; both courses can be attended in parallel.


Your final grade will be calculated as the the weighted average of:

Following the D-INFK guidelines for doctoral studies, PhD students get credit points according to the same rules that apply for Bachelor or Master students. That is, with a final grade of at least 4 (calculated as explained above) you will receive 7KE, and 0KE otherwise.

Lecture Notes

The lecture notes can be found here.


The exercise classes are an integral part of the course. Thus, we strongly recommend you to attend them regularly and solve the weekly exercise sheets.

Exercise Sheet 1

Exercise Sheet 1 Solutions

Exercise Sheet 2

Exercise Sheet 2 Solutions

Exercise Sheet 3

Exercise Sheet 3 Solutions

Graded Homework Sheet 1

Common Mistakes 1

Exercise Sheet 4

Exercise Sheet 4 Solutions

Exercise Sheet 5

Exercise Sheet 5 Solutions

Graded Homework Sheet 2

Common Mistakes 2

Exercise Sheet 6

Exercise Sheet 6 Solutions

Exercise Sheet 7

Exercise Sheet 7 Solutions

Graded Homework Sheet 3

Common Mistakes 3

Exercise Sheet 8

Exercise Sheet 8 Solutions

Exercise Sheet 9

Exercise Sheet 9 Solutions


This pdf contains a short introduction to big-oh notation, asymptotics and it also contains some useful inequalities.

LaTex template. To save the LaTex template, you need to right-click on the link and the "save then target" wherever you want to save it. Just clicking on the link will not be of much use, as you will just see the squeezed LaTex code.



Linearity of expectation

Markov and Chebyshev inequalities

First and second moment method

Chernoff bounds

Negative Correlation

Janson, Azuma and Talagrand inequalities

Markov chains

Outlook (if time permits)