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 / HS 2
Heiko Röglin
Tutorials
Monday, 12:30 - 14:00
Wednesday, 10:15 - 11:45
AVZ III / A6b
AVZ III / A6b
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

Contents

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


Exams

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.


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.