Randomized Algorithms

Modulnummer
TI5008
Modulverantwortliche
Hellwig Geisse
Dozenten
Hellwig Geisse
Kurzbeschreibung
This course shows how randomness can be used in the design of algorithms, which would have unreasonable long running times in the deterministic case.
Qualifikations- und Lernziele

The students know how randomized algorithms work, the princi-ples that guide their development, and how to prove their proper-ties. They defend their own evidence in the exercises.

Lerninhalte
  • Basics
  • Ouwitting the adversary
  • Fingerprinting
  • Probability amplification by repetition and teh method of random tests
  • Frequent witnesses
  • Optimization and randomized rounding
Moduldauer (Semester)
1
Unterrichtssprache
Deutsch
Gesamtaufwand
6 CrP; 180 Stunden, davon etwa 60 Stunden Präsenzzeit.
Semesterwochenstunden
4
Lernformen
Lecture 2 sppw Exercises 2 sppw
Geprüfte Leistung
Written or oral exam (The form of the examination will be announced to the students in a timely and appropriate manner)
Bewertungsstandard
according to examination regulations (§ 9)
Häufigkeit des Angebots
As Needed
Literatur
  • J. Hromkovic: Randomisierte Algorithmen Teubner
  • R. Motwani: Randomized Algorithms Cambridge University Press