Pearls of Algorithms
Part 2: Probabilistic Analysis and Randomized Algorithms

General Information

What When Where Lecturer
Lectures
Monday, 14:30 - 16:00
Wednesday, 8:30 - 10:00
AVZ III / A207
AVZ III / A207
Heiko Röglin
Tutorials
Wednesday, 12:30 - 14:00
Thursday, 12:30 - 14:00
LBH / II.57
LBH / II.57
Vlad Berindei

Part 1 of this lecture was given by Norbert Blum.
Part 3 of this lecture was given by Rolf Klein.
Part 4 of this lecture was given by Marek Karpinski.

Contents

Date Contents Course Materials
November 5
1. Basic Probability Theory and Randomized Algorithms
1.1 Discrete Probability Spaces
1.2 Independent Events and Conditional Probability
Chapter 1 in [MU05]
November 7
1.3 Verifying Matrix Multiplication
1.4 Application: A Randomized Min-Cut Algorithm
Chapter 1 in [MU05]
November 12
1.4.1 Contract Algorithm
Chapter 1 in [MU05]
November 14
1.4.2 FastCut Algorithm
Chapter 10.2 in [MR95]
November 19
2. Smoothed Analysis
2.1 Introduction to Smoothed Analysis
November 21
2.2 Smoothed Analysis of the 2-Opt Algorithm for the TSP
November 26
2.3 Smoothed Analysis of the Knapsack Problem

Problem Sets


Exams

Students can take the oral exam with Professor Blum, Professor Karpinski, Professor Klein, 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 4 and February 5. Re-exams will be on March 19. Students should send an email to Antje Bertram to schedule the exam.


References

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.