Randomized Algorithms
Winter 02/03
Many algorithmic problems have a simple, elegant and
efficient solution if one allows randomization, i.e.,
decisions of the algorithm are not only based on the input
but also on the value of some random event, e.g., a coin flip.
Examples come from such diverse area as sorting, load balancing parallel
computers, optimization, logics, computational geometry, statistics,...
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
A course in algorithms and data structures.
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
Exercises
Exercise 1
Exercise 2
Exercise 3
Exercise 4
Exercise 5
Exercise 6
Possible Topics for Talks