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 2-Opt Algorithm for the TSP
January 24
3. Smoothed Analysis of the 2-Opt Algorithm for the TSP (continued)
January 26
4. k-Means Clustering
4.1 Smoothed Analyis of the k-Means Method
4.2 k-Means++
Chapters 5 and 6 in [Art09]
January 31
4.2 k-Means++ (continued)
Chapter 6 in [Art09]
February 2
5. The Min-Cut Problem
Chapter 2 in [Vö02]
Chapter 10.2 in [MR95]

Problem Sets

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