Randomized Algorithms
General Info
- Lecturer:
Prof. Dr. Susanne Albers
- Module:
IN2160
- Area:
4+2 lectures per week in
area III (Theoretical Computer Science)
core course, topic algorithms
- Time and Place:
Monday, 14:00–16:00,
Wednesday, 16:00–18:00, 00.13.009A
- Exercises (web page):
2 hours per week exercises accompanying the lectures
Wednesday, 14:00–16:00, 03.11.018
Teaching assistant: Dr. Dimitrios Letsios
- 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
- 07/10/2014
First lecture on 08/10/2014 at 16:00.
- 08/10/2014
No exercise session on 08/10/2014.
- 15/12/2014
Extra lecture on 17/12/2014 at 14:00.
- 03/02/2015
Final Examination on Friday 06/02/2015.
Time: 10:30-12:30.
Room: 00.04.011.
- 10/02/2015
The meeting for questions on the marks of the exam will take place on Friday 13/02/2015.
Time: 14:00-15:00.
Room: 02.09.014.
- 14/04/2015
The meeting for questions on the marks of the repeat exam will take place on Friday 17/04/2015.
Time: 14:00-15:00.
Office: 03.09.55.
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 8, 2014: Basic results; randomized quicksort; [MR] pages 3-5.
- October 13, 2014: Basic results; randomized quicksort continued; min-cut algorithm; [MR] pages 6-9.
- October 15, 2014: Basic results; binary planar partitions; verifying matrix multiplication; a probabilistic recurrence; [MR] pages 11-15 and [MU] pages 8-10.
- October 20, 2014: Basic results; a probabilistic recurrence continued; complexity classes; [MR] page 16 and 21-22.
- October 22, 2014: Game-theoretic techniques; game tree evaluation; [MR] pages 28-30.
- October 27, 2014: Game-theoretic techniques; von Neumann's minimax theorem; Yao's technique; [MR] pages 31-34.
- October 29, 2014: Game-theoretic techniques; Yao's technique continued; a lower bound for game tree evaluation; [MR] pages 35-37.
- November 3, 2014: Game-theoretic techniques; randomness and non-uniformity; [MR] pages 38-39.
- November 5, 2014: Moments and deviations; occupancy problems; bucket sort; [MR] pages 43-45 and [MU] page 94.
- November 10, 2014: Moments and deviations; bucket sort continued; inequalities by Markov and Chebyshev; [MR] pages 45-47.
- November 12, 2014: Moments and deviations; median algorithm; [MU] pages 53-57.
- November 24, 2014: Moments and deviations; median algorithm continued; two-point sampling; [MU] pages 53-57 and [MR] pages 51-53, .
- November 26, 2014: Moments and deviations; two-point sampling continued; coupon collector's problem; [MR] pages 51-53, and [MU] pages 33 and 50-52.
- December 1, 2014: Moments and deviations; stable marriage problem, [MR] pages 53-57. Chernoff bounds; moment generating functions; [MU] page 61.
- December 3, 2014: Chernoff bounds; moment generating functions; deriving Chernoff bounds; bounds for Poisson trials; [MU] page 62-66.
- December 8, 2014: Chernoff bounds; coin flips; parameter estimation; a better bound for a special case; set balancing; [MU] pages 67-70.
- December 10, 2014: Chernoff bounds; set balancing; packet routing on the hypercube; [MU] pages 71-73.
- December 15, 2014: Chernoff bounds; packet routing on the hypercube; [MU] pages 74-75.
- December 17, 2014: Chernoff bounds; packet routing on the hypercube; a wiring problem; [MU] pages 76-78 and [MR] pages 79-82.
- January 7, 2015: Chernoff bounds; a wiring problem; [MR] pages 79-82. The probabilistic method; [MU] page 126.
- January 12, 2015: The probabilistic method; the basic counting argument; the expectation argument; [MU] pages 127-130.
- January 14, 2015: The probabilistic method; the expectation argument; [MU] pages 130-132.
- January 19, 2015: The probabilistic method; sample and modify; [MU] page 133. Data structures; treaps; [MR] 201-208.
- January 21, 2015: Data structures; treaps; [MR] 201-208.
- January 25, 2015: Data structures; treaps; [MR] 201-208.
- January 27, 2015: Data structures; treaps; [MR] 216-220.
Literature
- [MU] M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic
Analysis. Cambridge University Press, 2005.
- [MR] R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
July 2022: Jens Quedenfeld completed his doctoral degree.
June 2022: Maximilian Janke completed his doctoral degree.
March 2022: Alexander Eckl completed his doctoral degree.
June 2021: Leon Ladwig completed his doctoral degree.
February 2020: The Program Committee of SWAT 2020 is chaired by Susanne Albers.
February 2020: Susanne Albers is invited speaker at the ACM India Annual Event.
ESA/ALGO 2019 will be organized by Susanne Albers and her group.
May 2019: Susanne Albers is invited speaker at the symposium 50 Years Informatics
July 2019: Susanne Albers is invited speaker at SIROCCO 2019, Italy.
December 2017: Susanne Albers will give keynote address at the
Graduation Day, Department of Computer Science at RWTH Aachen University.
April 2017: New Research Training Center AdONE, funded by the German Research Foundation.
Susanne Albers receives ERC Advanced Grant. Press release of the Bavarian State Ministry of the Sciences, Research and the Arts.
August 2016: Susanne Albers is keynote speaker at Euro-Par 2016,
Grenoble.
Susanne Albers, Nicole Megow and Andreas S. Schulz will organize MAPSP 2017.
Juni 2016: Susanne Albers gives an invited lecture at the Academy of Sciences and
Literature, Mainz.
September 2015: Susanne Albers is invited speaker at
MPI-INF – 25th Anniversary.
The program features several Turing Award winners,
Leibniz Prize winners, Humboldt Prize winners and ERC Grant winners.
June 2015: Susanne Albers is keynote speaker at the 31st International Symposium on Computational Geometry (SOCG15), Eindhoven.
June 2015: Susanne Albers is invited speaker of the tutorial on Network Creation Games: How Does the Internet Form?
organized by Erik D. Demaine (MIT) and MohammadTaghi Hajiaghayi (University of Maryland).
16th Conference on Electronic Commerce (EC15), Portland, Oregon.
