Prof. Dr. Tobias Friedrich

Probability and Computing

MSc Lecture - Summer 2021



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 in the lecture will be done during the first weeks of this lecture.

The topics of this lecture will include:


  • Randomised Algorithms
  • The Markov chain Monte Carlo method
  • The probabilistic method and the Lovasz local lemma
  • Random structures and phase transitions
  • Discrete time stochastic 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.

Timeslots and venue

  • Mondays: 13:30-15:00 via Zoom (link will be provided in the moodle)
  • Wednesdays: 15:15-16:45 via Zoom (link will be provided in the moodle)