Prof. Dr. Tobias Friedrich

Probability and Computing

MSc Lecture - Summer 2023



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. Successful hand in of homework (at least 50%) is required for students to participate in the final exam. The grade is determined by the final exam.


Timeslots and venue

  • Mondays: 15:15-16:45 at HS 3
  • Tuesdays: 15:15-16:45 at HS 3 (except on 18.04, du to relocation to K-1.02)