![[MPI Logo] HEIGHT=84 WIDTH=142](mpiilogo.gif)
![[InfoLogo] HEIGHT=84 WIDTH=142](logo.gif)
Randomized Algorithms
Winter 05/06
![[MotRag]](MotRag.gif)
![[MitzUpf]](UpfalBook.gif)
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 books by Motwani/Raghavan
(Cambridge University Press, 1995) and Mitzenmacher/Upfal (Cambridge University Press, 2005),
and selected papers.
Prerequisites
Basic knowledge in algorithms and data structures.
Topics
- Occupancy problems (Balls and Bins, Hashing, Bloom Filters) (R. Beier)
- Game-theoretic Techniques (S. Canzar)
- The Probabilistic Method and the Lovasz Local Lemma (S. Funke)
- Markov Chains (S. Funke)
- Randomized Rounding (S. Canzar)
- Randomized LP Solving (S. Canzar)
Further Information
- Lectures: Tuesday, 14:15-15:45, Location: MPI, room 024
- First Lecture: Tuesday, October 18th
- Tutorials: each Monday 16:15-17:45, MPI, room 024,
- Language: English
- Lecturers
- Dr. Rene Beier, Building 46, R.312,
Homepage
Dipl.-Inform. Stefan Canzar,Homepage
Dr. Stefan Funke, Building 46, R.308,Homepage
Exercises
Exercise sheet 1 PS PDF (Due Date: 25.10.05)
Exercise sheet 2 PS PDF (Due Date: 10.11.05)
Exercise sheet 3 PS PDF (Due Date: 24.11.05)
Exercise sheet 4 PS PDF (Due Date: 08.12.05)
Exercise sheet 5 PS PDF (Due Date: 12.01.05)
CORRECTION: The algorithm for problem 3 might have exponential dependency on 1/eps!
Exercise sheet 6 PS PDF (Due Date: 26.01.05)
Lecture Notes
1st lecture here.
Probabilistic Analysis of the Knapsack problem here (see also here and here).