Termine
|
Art
|
Termin / Ort
|
Beginn
|
Dozent
|
|
V2
|
Fr 10:00 - 11:30 / 4017 | 13.04.07 |
Vöcking |
|
Ü1
|
Mo 10:00 - 11:30 / 5056 | 07.05.07 |
Fanghänel |
Die Übung findet jeweils jede zweite Woche statt, beginnend am Montag, dem 07.05.2007.
Inhalt
Die Vorlesung gibt einen Überblick über randomisierte Algorithmen.
Part 1 - Introduction to Randomized Algorithms
- Contention Resolution (KT-Book Section 13.1)
- Random Variables and Expectations (KT-Book Section 13.3)
- Randomized Quicksort (
, 94 kB)
- Randomized Median Finding (KT-Book Section 13.5, first half)
- Hashing/Dictionaries (KT-Book Section 13.6)
- Closest Pair of Points (KT-Book Section 13.7)
- Chernoff Bounds (KT-Book Section 13.9)
Part 2 - Probabilistic Analysis of Algorithms
- Lecture Notes (, 290 kB)
Part 3 - Selected Topics from Randomized Algorithms
- Load Balancing (, 124 kB)
- Markov Chains and Random Walks(, 114 kB)
- Game Tree Evaluation/Yaos Principle (, 106 kB)
- Evolutionary Algorithms (not relevant for exam)
Material
- Übungsaufgaben
Die Übungsblätter werden jede zweite Woche ausgegeben, und die Bearbeitungszeit ist eine Woche. Die Abgabe soll am Freitag eine Woche nach der Ausgabe bis spätestens 12:00 Uhr im Übungskasten vor dem Lehrstuhl Informatik 1 erfolgen. Die Übungsblätter werden dann in der Woche nach der Abgabe in den Übungsgruppen besprochen.
- Übungsblatt 1: , 55 kB
- Übungsblatt 2: , 53 kB
- Übungsblatt 3: , 51 kB
- Übungsblatt 4: , 48 kB
- Übungsblatt 5: , 38 kB
Das erste Übungsblatt wird am Freitag, dem 20.04., ausgegeben und soll bis zum folgenden Freitag, dem 27.04., bearbeitet werden.
- Übungsblatt 1: