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 MinCut 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 2Opt Algorithm for the TSP


November 26  2.3 Smoothed Analysis of the Knapsack Problem

Problem Sets
 Problem Set 2.1 (to be discussed on Nov 14 and Nov 15)
 Problem Set 2.2 (to be discussed on Nov 21 and Nov 22)
 Problem Set 2.3 (to be discussed on Nov 28 and Nov 29)
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. Reexams 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". [MR95] Rajeev Motwani und Prabhakar Raghavan. Randomized Algorithms.ISBN: 9780521474658, Cambridge University Press, 1995.
 [MU05] Michael Mitzenmacher und Eli Upfal. Probability and Computing.ISBN: 9780521835404, Cambridge University Press, 2005.