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.
A course in algorithms and data structures.
- 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)
- Privatdozent Dr. Peter Sanders, Building 46, R.308,
Dr. Ernst Althaus, Building 46, R.304,firstname.lastname@example.org
Possible Topics for Talks