Randomized Algorithms
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.

Prerequisites

Further Information

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 Notes

• 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

Exercises

Exercise 1

Exercise 2

Exercise 3

Exercise 4

Exercise 5

Exercise 6