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, 08:00 – 10:00, 00.08.038
Wednesday, 8:00 – 10:00, 00.13.009A 
Exercises (web page):
2 hours per week exercises accompanying the lectures
Wednesday, 10:00–12:00, Room 03.11.018
Teaching assistant: Dr. Yiannis Giannakopoulos

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 and present at least twice their solutions in the tutorial class. 
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 17, 2016There will be no class on December 7, 2016 (Dies academicus)
Exam date: March 2nd, 2017 (Interims Hörsaal 1, 11:30)
Exam review: March 14th, 2017. Room 03.11.018, 14:00
Repeat exam date: April 18th, 2017 (Hörsaal 2, 10:30)
You can bring with you a doublesided A4size paper sheet with handwritten (NOT printed) notes. No calculators allowed.
Repeat Exam review: Thursday, April 27th, 2017. Office 03.09.055.
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 19, 2016 (two lectures): Basic results; randomized quicksort; mincut algorithm; [MR] pages 37.
 October 24, 2016: Basic results; mincut algorithm continued; binary planar partitions; [MR] pages 811.
 October 26, 2016 (two lectures): Basic results; binary planar partitions; verifying matrix multiplication; [MR] pages 1114 and [MU] pages 810.
 October 31, 2016: Basic results; a probabilistic recurrence; complexity classes; [MR] pages 1516 and 21.
 November 2, 2016: Basic results; complexity classes continued; Gametheoretic techniques; game tree evaluation; [MR] pages 2223 and 2829.
 November 7, 2016: Gametheoretic techniques; game tree evaluation; von Neumann's minimax theorem; [MR] pages 2931.
 November 9, 2016: Gametheoretic techniques; von Neumann's minimax theorem continued; Yao's technique; [MR] pages 3234.
 November 14, 2016: Gametheoretic techniques; Yao's technique continued; a lower bound for game tree evaluation; [MR] pages 3437.
 November 16, 2016: Gametheoretic techniques; a lower bound for game tree evaluation; randomness and nonuniformity; [MR] pages 3739.
 November 21, 2016: Gametheoretic techniques; randomness and nonuniformity; Moments and deviations; occupancy problems; [MR] pages 3940 and 4344.
 November 28, 2016: Moments and deviations; occupancy problems; bucket sort; [MR] pages 4445 [MU] pages 9293.
 November 30, 2016: Moments and deviations; bucket sort; inequalities by Markov and Chebyshev; [MU] pages 94 and 4449.
 December 5, 2016: Moments and deviations; median algorithm; [MU] pages 5355 and [MR] pages 4749.
 December 12, 2016: Moments and deviations; median algorithm continued; twopoint sampling; [MU] pages 5557 and [MR] pages 5152.
 December 14, 2016: Moments and deviations; twopoint sampling continued; coupon collector's problem; [MR] pages 5253 and [MU] page 33.
 December 19, 2016: Moments and deviations; coupon collector's problem continued; stable marriage problem; [MU] pages 5055 and [MR] pages 5354.
 December 21, 2016: Moments and deviations; stable marriage problem continued; Chernoff bounds; moment generating functions; deriving Chernoff bounds; Poisson trials; [MR] page 5657 and [MU] pages 6164.
 January 9, 2017: Chernoff bounds; deriving Cheroff bounds for Possoin trials; coin flips; parameter estimation; [MU] pages 6468.
 January 11, 2017: Chernoff bounds; parameter estimation continued; a better bound for a special case; set balancing; [MU] pages 6872.
 January 16, 2017: Chernoff bounds; packet routing on the hypercube; [MU] pages 7274.
 January 18, 2017: Chernoff bounds; packet routing on the hypercube; [MU] pages 7576.
 January 23, 2017: The probabilistic method; the basic counting argument; [MU] pages 126128.
 January 25, 2017: The probabilistic method; the expectation argument; [MU] pages 128132.
 January 30, 2017: The probabilistic method; sample and modify; Data structures; treaps; [MU] page 133 and [MR] 201208.
 Februar 1, 2017: Data structures; treaps; [MR] 201208.
 February 6, 2017: Data structures; treaps; [MR] 201208.
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.