After successful completion of the course, students are able to... 

• Explain terms and strategies associated with randomized algorithms; 
• Intuitively and formally describe randomized algorithms for various problems, analyze them mathematically, and prove their properties;
• Apply probability calculations to analyze the performance of randomized algorithms;
• Identify application areas of randomized algorithms and select suitable algorithms for solving a given problem;
• Analyze unknown computational problems and design and analyze their own randomized solution procedures.

Randomized algorithms are algorithms that make random decisions during their execution. Such approaches can significantly simplify or speed up the computation. However, we concede that the algorithms may produce incorrect results with a certain, limited probability, or that the algorithms are efficient only with a certain probability. This lecture covers fundamental principles, techniques, and applications of randomized algorithms. Through examples, we study their development and analysis, particularly with regard to limiting the error probability and demonstrating efficiency.

Possible topics include:

• Markov Chains, Random Walks and their applications
• Application of expected values and bounds on the deviation from them, concentration bounds
• The Monte Carlo method
• Randomized sorting algorithms
• The probabilistic method, applications, and derandomization
• Hashing and Bloom filters
• Linear programming and random rounding techniques
• Randomized complexity classes and theory

Lectures and exercise units

• Solve and hand-in exercise sheets with theoretical questions
• Present and discuss the course content in an oral exam

The final grade is a combination of the performance in the exercises and the oral exam.