English English

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 (pdf, 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)
KT-Book: Algorithm Design, J. Kleinberg and E. Tardos, 2005

Part 2 - Probabilistic Analysis of Algorithms

Part 3 - Selected Topics from Randomized Algorithms

  • Load Balancing (pdf, 124 kB)
  • Markov Chains and Random Walks(pdf, 114 kB)
  • Game Tree Evaluation/Yaos Principle (pdf, 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.

    Das erste Übungsblatt wird am Freitag, dem 20.04., ausgegeben und soll bis zum folgenden Freitag, dem 27.04., bearbeitet werden.