Winter 02/03

This course teaches techniques for the design and analysis of randomized algorithms. The course is based on the book by Motwani and Raghavan (Cambridge University Press, 1995) and selected papers.

- Lectures: Friday, 09:00-11:00, Building 46, Room: 024 (changed!)
- Exercises: Wednesday, 17:30-18:30, Building 46, Room: 023 (in the weeks after returning exercises)
- Lecturers
- Privatdozent Dr. Peter Sanders, Building 46, R.308,
sanders@mpi-sb.mpg.de

Dr. Ernst Althaus, Building 46, R.304,althaus@mpi-sb.mpg.de

- Lecture 1: Introduction, Quicksort, Simple Min-Cuts. Here is a very compact analysis of quicksort.
- Lecture 2:Faster Min-Cuts.
- Lecture 3:Games.
- Lecture 4:Occupancy Problems and Chernoff Bounds. The derivations of Chernoff bounds by Dubhashi and Panconesi.
- Lecture 5: Applications of Chernoff Bounds: Maximum Occupancy (slides 16-20), Very Fast Median Selection (slides 21,22), Parallel Priority Queues (slides).
- Lecture 6/7:Optimal Multiple Choice Allocation.
- Lecture 7: The Method of Bounded Difference (slides 23-24) The formulation is implicit in Motwani-Raghavan but we took it from Dubhashi-Panconesi.
- Lecture 8: Markov Chains and Random Walks. Derandomization.
- Lecture 9: Algebraic Methods.
- Lecture 10: Random Incremental Construction and Random Sampling.
- Lecture 11: Linear Programming and Extensions
- Lecture 12: Minimum Spanning Trees
- Lecture 13: Randomized Rounding