Analyse randomisierter Algorithmen
Veranstalter
Prof. Dr. Petra Berenbrink
Abhaltungszeiten
- Vorlesung und Übung: Dienstags, 8:30 - 11:45
- Seminar: Geblockt
Abhaltungsort
- Per Videokonferenz
Seminar
Das Seminar findet am Semesterende statt. Die vergebenen Themen sollen im Seminar präsentiert und schriftlich ausgearbeitet werden. Die Präsentation soll pro Person ca. 35-45 Minuten dauern, die schriftliche Ausarbeitung ca. 10-20 Seiten umfassen.
Die Ausarbeitung ist bis zum 28. Februar per E-Mail abzugeben.
Mündliche Prüfung
Abschließend ist eine mündliche Prüfung zu absolvieren. Die Termine werden individuell vergeben. Terminvereinbarung bitte per E-Mail an die Lehrveranstaltungsleitung.
Unterlagen
Slides
Übungsblätter
Hier werden regelmäßig Übungsblätter erscheinen. Lösungen werden in den Übungen von den Studierenden vorgetragen und zusammen diskutiert.
Literatur
Die Vorlesungsmaterialien sind auf Englisch. Die Vorlesung basiert unter anderem auf folgender Literatur:
- Randomized Algorithms. Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press, 1995
- Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Michael Mitzenmacher and Eli Upfal, Cambridge University Press, 2005
- Concentration of Measure for the Analysis of Randomised Algorithms. Devdatt P. Dubhashi and Alessandro Panconesi, Cambridge University Press, 2009