Lectures Efficient Algorithms and
Data Structures I Randomized Algorithms Fundamental Algorithms Seminar Selected Topics in Efficient Algorithms Lab Course Algorithms for Programming Contests

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
  

Announcements

Content

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.

Literature

• [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.