[MPI Logo] HEIGHT=84 WIDTH=142 [InfoLogo] HEIGHT=84 WIDTH=142

Randomized Algorithms
Winter 02/03

[MotRag] 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