Pearls of AlgorithmsPart 3: Probabilistic Analysis and Randomized Algorithms
Monday, 15:15 - 16:45Wednesday, 9:15 - 10:45
AVZ III / HS 1AVZ III / A 301
Wednesday, 15:15 - 16:45Thursday, 13:30 - 15:00
AVZ III / A 6aAVZ III / A 6a
Part 1 of this lecture was given by Norbert Blum
Part 2 of this lecture was given by Marek Karpinski and Mathias Hauptmann
1. Introduction to Smoothed Analysis
2. Smoothed Analysis of the Knapsack Problem
2. Smoothed Analysis of the Knapsack Problem (continued)
3. Smoothed Analysis of the 2-Opt Algorithm for the TSP
3. Smoothed Analysis of the 2-Opt Algorithm for the TSP (continued)
4. k-Means Clustering
4.1 Smoothed Analyis of the k-Means Method
Chapters 5 and 6 in [Art09]
4.2 k-Means++ (continued)
Chapter 6 in [Art09]
5. The Min-Cut Problem
Chapter 2 in [Vö02]
Chapter 10.2 in [MR95]
- 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)
ExamsExams 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.
- [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: 978-0521474658, 1995.
- [ST09] Daniel A. Spielman and Shang-Hua Teng.Communications of the ACM, 52(10):76-84, 2009.
- [Vö02] Berthold Vöcking.TU Dortmund, Winter 2002/03.