Randomized Algorithms (MuA)
News
Content
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
algorithms.
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]
Exam
Oral examinations after the course.
Schedule

Lecture:
Day Time Room Wed. 9:1510:45 D2

Tutorials:
Day Time Room Wed. 12:0012:45 A4
Teaching material
Lecture  Slides (als PDF)  Literature 

6.4.2011  Introduction, Quicksort, MinCut  [Motwani]: 39 
13.4.2011  Randomized shortest paths  [Motwani]: 278283 
20.04.2011  Randomized shortest paths  [Motwani]: 283286 
27.04.2011  Randomized shortest paths  [Motwani]: 286288 
04.05.2011  Randomized primality test  [Cormen]: 876887 
11.05.2011  Chernoff bounds  [Motwani]: 4547, 6773 
25.05.2011  The probabilistic method  [Motwani]: 101104, 108110 
08.06.2011  Lovasz Local Lemma, Markov chains  [Motwani]: 115118, 129132 
15.06.2011  Random walks in graphs  [Mitzenmacher]: 174177 
22.06.2011  Randomized data structures  [Motwani]: 201204, 206208 
02.12.2010  Randomized data structures  [Motwani]: 206213 
06.01.2011  Randomized data structures, random graphs 
Exercises
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
Bonus points
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.
Literature
 Motwani, Raghavan: "Randomized Algorithms",
Cambridge University Press, ISBN: 0521474655  Mitzenmacher, Upfal: "Probability and Computing 
Randomized Algorithms and Probabilistic Analysis",
Cambridge University Press, ISBN: 0521835402  Cormen, Leiserson, Rivest, Stein: "Introduction
to Algorithms",
The MIT Press, ISBN: 0262032937