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:
To successfully complete the module students must obtain at least 50% of the points in the written exam. A bonus of 0.3 in the final grade will be granted if students achieve at least 50% of the points in the homework assignments. -
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
There will be no class on October 12, 2015 as that day is Dies Academicus.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.
- October 14, 2015 (two lectures): Basic results; randomized quicksort; min-cut algorithm; [MR] pages 3-8.
- October 19, 2015: Basic results; min-cut algorithm conitnued; binary planar partitions; [MR] pages 8-11.
- October 21, 2015: Basic results; binary planar partitions continued; [MR] pages 13-14.
- October 26, 2015: Basic results; verifying matrix multiplication; a probabilistic recurrence; [MU] pages 8-10 and [MR] page 15 and 21-22.
- October 28, 2015: Basic results; a probabilistic recurrence continued; complexity classes; [MR] pages 15, 16 and 21.
- November 2, 2015: Basic results; complexity classes; Game-theoretic techniques; game tree evaluation; [MR] pages 22-23 and 28.
- November 4, 2015: Game-theoretic techniques; game tree evaluation, von Neumann's minimax theorem; [MR] pages 29-31.
- November 9, 2015: Game-theoretic techniques; von Neumann's minimax theorem continued; Yao's technique; [MR] pages 32-35.
- November 11, 2015: Game-theoretic techniques; Yao's technique continued; a lower bound for game tree evaluation; [MR] pages 35-37.
- November 16, 2015: Game-theoretic techniques; randomness and non-uniformity; [MR] pages 38-40.
- November 18, 2015: Moments and deviations; occupancy problems; [MR] pages 43-45.
- November 23, 2015: Moments and deviations; bucket sort; inequalities by Markov and Chebyshev; [MU] page 94 and [MR] pages 45-47.
- November 25, 2015: Moments and deviations; median algorithm; [MU] pages 53-56.
- November 30, 2015: Moments and deviations; median algorithm continued; two-point sampling; [MU] pages 56-57 and [MR] pages 51-52, .
- December 2, 2015: Moments and deviations; two-point sampling continued; coupon collector's problem; [MR] pages 52-53, and [MU] pages 33 and 50-52.
- December 7, 2015: Moments and deviations; stable marriage problem, [MR] pages 53-57. Chernoff bounds; moment generating functions; [MU] page 61.
- December 9, 2015: Chernoff bounds; moment generating functions; deriving Chernoff bounds; bounds for Poisson trials; [MU] page 62-66.
- December 14, 2015: Chernoff bounds; coin flips; parameter estimation; a better bound for a special case; set balancing; [MU] pages 67-72.
- December 16, 2015: Chernoff bounds; packet routing on the hypercube; [MU] pages 72-75.
- December 21, 2015 (two lectures): Chernoff bounds; packet routing on the hypercube; a wiring problem; [MU] pages 75-78 and [MR] pages 79-82.
- January 11, 2016: The probabilistic method; the basic counting argument; the expectation argument; [MU] page 126-130.
- January 13, 2016: The probabilistic method; the expectation argument; sample and modify; [MU] pages 130-132.
- January 18, 2016: The probabilistic method; sample and modify; Data structures; treaps; [MU] page 133 and [MR] 201-208.
- January 20, 2016: Data structures; treaps; [MR] 201-208.
- January 25, 2016: Data structures; treaps; [MR] 201-208.
- January 27, 2016: Data structures; universal hashing; [MR] 216-220.
- February 1, 2016: Data structures; perfect hashing; [MU] 326-328 and [MR] 221-229.
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.