Pearls of Algorithms
Part 2: Probabilistic Analysis and Randomized Algorithms

General Information

What When Where Lecturer
Monday, 14:30 - 16:00
Wednesday, 8:30 - 10:00
AVZ III / A207
Heiko Röglin
Monday, 12:30 - 14:00
Wednesday, 10:15 - 11:45
Matthias Kretschmer

Part 1 of this lecture was given by Norbert Blum

Part 3 of this lecture was given by Marek Karpinski and Mathias Hauptmann


Date Contents Course Materials
November 14
1. Basic Probability Theory and Randomized Algorithms
1.1 Discrete Probability Spaces
1.2 Independent Events and Conditional Probability
Chapter 1 in [MU05]
November 16
1.3 Verifying Matrix Multiplication
Chapter 1 in [MU05]
November 21
1.4 Application: A Randomized Min-Cut Algorithm
1.4.1 Contract Algorithm
Chapter 1 in [MU05]
November 23
1.4.2 FastCut Algorithm
Chapter 10.2 in [MR95]
November 28
1.5 Discrete Random Variables and Expectation
1.5.1 Application: Quicksort
Chapter 2 in [MU05]
November 30
1.5.2 Application: Coupon Collector's Problem
1.5.3 Markov's Inequality
1.6 Continuous Distributions
Chapter 2 in [MU05]
Chapter 3.1 in [MU05]
Chapter 8.1 in [MU05]
December 5
2. Smoothed Analysis
2.1 Introduction to Smoothed Analysis
December 7
no lecture due to Dies Academicus
December 12
2.2 Smoothed Analysis of the 2-Opt Algorithm for the TSP
December 14
2.3 Smoothed Analysis of the Knapsack Problem

Problem Sets


Students can take the oral exam with Professor Blum, Professor Karpinski, or Professor Röglin. The exam will cover the whole semester, regardless of which examiner is chosen.

Exams with Heiko Röglin can be taken on February 8 and February 9. Re-exams will be on March 29. Students should send an email to Heiko Röglin to schedule the exam.


There are lecture notes available for "2. Smoothed Analysis".

The following two books, which are available in the reading room (AVZ III / A125), cover the topics discussed in "1. Basic Probability Theory and Randomized Algorithms". The Bachelor's course about randomized algorithms also covers some of the topics discussed in this class.