Randomization as well as probabilistic techniques play an important role in the design and
analysis of many efficient algorithms. In this lecture, we consider two fundamental ways in which
randomness comes to bear in algorithms: randomized algorithms and the probabilistic analysis of
Randomized algorithms are algorithms that make random choices during their execution. In many important cases, randomized procedures are significantly more efficient than the best known deterministic solutions. Furthermore, in most cases they are also simpler and easier to implement. These gains come at a price; the answer may have some probability of being incorrect, or the efficiency is guaranteed only with some probability. However, if the probability of error is sufficiently small, then the improvement in speed or memory requirements may be worthwhile.
[Michael Mitzenmacher and Eli Upfal: Pobability and Computing]
Oral examinations after the course.
Day Time Room Wed. 9:15-10:45 D2
Day Time Room Wed. 12:00-12:45 A4
|Lecture||Slides (als PDF)||Literature|
|6.4.2011||Introduction, Quicksort, Min-Cut||[Motwani]: 3-9|
|13.4.2011||Randomized shortest paths||[Motwani]: 278-283|
|20.04.2011||Randomized shortest paths||[Motwani]: 283-286|
|27.04.2011||Randomized shortest paths||[Motwani]: 286-288|
|04.05.2011||Randomized primality test||[Cormen]: 876-887|
|11.05.2011||Chernoff bounds||[Motwani]: 45-47, 67-73|
|25.05.2011||The probabilistic method||[Motwani]: 101-104, 108-110|
|08.06.2011||Lovasz Local Lemma, Markov chains||[Motwani]: 115-118, 129-132|
|15.06.2011||Random walks in graphs||[Mitzenmacher]: 174-177|
|22.06.2011||Randomized data structures||[Motwani]: 201-204, 206-208|
|02.12.2010||Randomized data structures||[Motwani]: 206-213|
|06.01.2011||Randomized data structures, random graphs|
Exercise sheet 1
Exercise sheet 2
Exercise sheet 3
Exercise sheet 4
Exercise sheet 5
Exercise sheet 6
Exercise sheet 7
Exercise sheet 8
Exercise sheet 9
Exercise sheet 10
Exercise sheet 11
Exercise sheet 12
There is a possibility to improve your grade in the final exam, if
- you achieve at least 50% of the points assigned to the exercises, which are corrected during the term. Then, you may obtain an upgrade of 1/3 .
- you achieve at least 80% of the points assigned to the exercises, which are corrected during the term. Then, you may obtain an upgrade of 2/3 .
- the best grade you can achieve is 1,0 (sehr gut).
- Important: you can not improve a grade of 5,0 (nicht bestanden) by bonus points.
- Motwani, Raghavan: "Randomized Algorithms",
Cambridge University Press, ISBN: 0-52-147465-5
- Mitzenmacher, Upfal: "Probability and Computing -
Randomized Algorithms and Probabilistic Analysis",
Cambridge University Press, ISBN: 0-521-83540-2
- Cormen, Leiserson, Rivest, Stein: "Introduction
The MIT Press, ISBN: 0-262-03293-7