Pearls of Algorithms
Part 3: Probabilistic Analysis and Randomized Algorithms
General Information
What  When  Where  Lecturer 

Lectures  Monday, 15:15  16:45
Wednesday, 9:15  10:45 
AVZ III / HS 1
AVZ III / A 301 
Heiko Röglin 
Tutorials  Wednesday, 15:15  16:45
Thursday, 13:30  15:00 
AVZ III / A 6a
AVZ III / A 6a 
Heiko Röglin 
Part 1 of this lecture was given by Norbert Blum
Part 2 of this lecture was given by Marek Karpinski and Mathias Hauptmann
Contents
Date  Contents  Course Materials 

January 12  1. Introduction to Smoothed Analysis 

January 17  2. Smoothed Analysis of the Knapsack Problem 

January 19  2. Smoothed Analysis of the Knapsack Problem (continued)
3. Smoothed Analysis of the 2Opt Algorithm for the TSP 

January 24  3. Smoothed Analysis of the 2Opt Algorithm for the TSP (continued) 

January 26  4. kMeans Clustering
4.1 Smoothed Analyis of the kMeans Method
4.2 kMeans++ 
Chapters 5 and 6 in [Art09]

January 31  4.2 kMeans++ (continued) 
Chapter 6 in [Art09]

February 2  5. The MinCut Problem 
Chapter 2 in [Vö02]
Chapter 10.2 in [MR95] 
Problem Sets
 Problem Set 3.1 (to be discussed on Jan 19 and Jan 20)
 Problem Set 3.2 (to be discussed on Jan 26 and Jan 27)
 Problem Set 3.3 (to be discussed on Feb 2 and Feb 3)
Exams
Exams with Heiko Röglin can be taken on February 10, February 17, or March 9. Students who would like to take an exam on any of these days should send an email to Heiko Röglin to schedule the exam.References
 [Art09] David Arthur.PhD Thesis, Stanford University, 2009.
 [AV07] David Arthur and Sergei Vassilvitskii.In Proceedings of SODA 2007.
 [AMR09] David Arthur, Bodo Manthey, and Heiko Röglin.In Proceedings of FOCS 2009.
 [MR95] Rajeev Motwani and Prabhaker Raghavan.Randomized Algorithms.Cambridge University Press, ISBN: 9780521474658, 1995.
 [ST09] Daniel A. Spielman and ShangHua Teng.Communications of the ACM, 52(10):7684, 2009.
 [Vö02] Berthold Vöcking.TU Dortmund, Winter 2002/03.