Prof. Dr. Tobias Friedrich

Probability and Computing

MSc Lecture - Summer 2021

People: Prof. Dr. Tobias Friedrich, Dr. Andreas Göbel
Links: Courses IT-Systems Engineering, Algorithm Engineering Moodle



The lecture will be held in English.

Probabilistic methods and Randomness are a central topic in modern computer science. This lecture will cover recent and classic breakthroughs in computer science that rely in theory of probabilities.

An introduction to the basic tools and concepts of probability theory that will be used will be held jointly with the lecture Theory of evolutionary algorithms.

The topics of this lecture will include:


  • Randomised Algorithms
  • The probabilistic method and the Lovasz local lemma
  • The Markov chain Monte Carlo method
  • Random structures and phase transitions
  • Discrete time random processes


The participants are expected to have basic mathematical knowledge and an interest in rigorous analysis of algorithms.  A background in probability theory is not required as a brief introduction to the basic mathematical tools and conceps will be covered in the lecture.


Students will be given homework bi-weekly. The successful hand in of homework is required for students to participate in the final exam.