This course shows how randomness can be used in the design of algorithms, which would have unreasonable long running times in the deterministic case.
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.
- Ouwitting the adversary
- Probability amplification by repetition and teh method of random tests
- Frequent witnesses
- Optimization and randomized rounding
Duration in Semester
6 CrP; an estimated 180 hours, of which approximately 60 are spent in class.
Weekly School Hours
Method of Instruction
Lecture 2 sppw Exercises 2 sppw
Requirements for the awarding of Credit Points
Written or oral exam (The form of the examination will be announced to the students in a timely and appropriate manner)
according to examination regulations (§ 9)
- J. Hromkovic: Randomisierte Algorithmen Teubner
- R. Motwani: Randomized Algorithms Cambridge University Press