Randomized Algorithms

Module Code
TI5008
Module Coordinators
Hellwig Geisse
Teachers
Hellwig Geisse
Short Description
This course shows how randomness can be used in the design of algorithms, which would have unreasonable long running times in the deterministic case.
Learning Objectives

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.

Contents
  • Basics
  • Ouwitting the adversary
  • Fingerprinting
  • Probability amplification by repetition and teh method of random tests
  • Frequent witnesses
  • Optimization and randomized rounding
Duration in Semester
1
Instruction Language
German
Total Effort
6 CrP; an estimated 180 hours, of which approximately 60 are spent in class.
Weekly School Hours
4
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)
Evaluation Standard
according to examination regulations (§ 9)
Availability
As Needed
References
  • J. Hromkovic: Randomisierte Algorithmen Teubner
  • R. Motwani: Randomized Algorithms Cambridge University Press