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.