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


December 14  2.3 Smoothed Analysis of the Knapsack Problem

Problem Sets
 Problem Set 2.1 (to be discussed on Nov 21 and Nov 23)
 Problem Set 2.2 (to be discussed on Nov 28 and Nov 30)
 Problem Set 2.3 (to be discussed on Dec 5)
 Problem Set 2.4 (to be discussed on Dec 12 and Dec 14)
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. Reexams 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". [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.