Randomisierte Algorithmen

What it is about

You learn fundamentals and techniques of randomized algorithms and how to estimate their running time and correctness with probabilistic methods. In the end you will be able to understand and analyze classical randomized algorithms (e.g., randomized Quicksort, Min-Cut, Treaps) and apply tools such as Markov, Chebyshev and Chernoff inequalities.

What you will be able to do

• Understanding of Las Vegas and Monte Carlo algorithms
• Knowledge of important randomized algorithms (e.g., Quicksort, Min-Cut, Treaps)
• Familiarity with probabilistic analytic tools (moments, Markov, Chebyshev, Chernoff)
• Application of the probabilistic method to combinatorial problems
• Use of game-theoretic techniques such as Yaos Minimax principle
• Understanding of universal and perfect hashing

What the module consists of

• LectureConveying the contents through talk and presentation
• TutorialWork on and discussion of exercise sheets; individual feedback through correction

Teaching method

• Lecture / PresentationIntroduction and explanation of theory and algorithms
• Exercise sheets and exercise discussionPractical application of what has been learned and individual feedback through corrections