Randomized Algorithms

General Info

  • Lecturer: Prof. Dr. Susanne Albers
  • Module: IN2160 TUMonline
  • Area:
    4+2 lectures per week in area III (Theoretical Computer Science)
    core course, topic algorithms
  • Time and Place:
    Monday, 10:00 – 12:00, 00.13.009A
    Wednesday, 8:00 – 10:00, 00.13.009A
  • Exercises (web page):
    2 hours per week exercises accompanying the lectures
    Date TBA
  • Course Certificate:
  • Audience:
    graduate students of computer science
    students with computer science as minor
  • Prerequisites:
    1st and 2nd year courses
    Efficient Algorithms and Data Structures is beneficial but not mandatory.
  • Recommended for:
    Extended knowledge in topic Algorithms



Over the past 25 years the design and analysis of randomized algorithms, which make random choices during their execution, has become an integral part of algorithm theory. For many problems, surprisingly elegant and fast randomized algorithms can be developed. In this lecture we will (a) study basic tools from probability theory needed in probabilistic analyses and (b) design randomized algorithms for a number of fundamental problems.


  • [MU] M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and ProbabilisticAnalysis. Cambridge University Press, 2005.
  • [MR] R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.