Universität Paderborn - Home Universität Paderborn
Die Universität der Informationsgesellschaft

Randomized Algorithms (MuA)



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]


Oral examinations after the course.


Teaching material


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


- Robert Elsässer