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:15-10:45 D2
-
Tutorials:
Day Time Room Wed. 12:00-12:45 A4
Teaching material
| 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 |
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: 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
to Algorithms",
The MIT Press, ISBN: 0-262-03293-7