LTI
LTI

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, 2016
There 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 double-sided A4-size 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; min-cut algorithm; [MR] pages 3-7.
  • October 24, 2016: Basic results; min-cut algorithm continued; binary planar partitions; [MR] pages 8-11.
  • October 26, 2016 (two lectures): Basic results; binary planar partitions; verifying matrix multiplication; [MR] pages 11-14 and [MU] pages 8-10.
  • October 31, 2016: Basic results; a probabilistic recurrence; complexity classes; [MR] pages 15-16 and 21.
  • November 2, 2016: Basic results; complexity classes continued; Game-theoretic techniques; game tree evaluation; [MR] pages 22-23 and 28-29.
  • November 7, 2016: Game-theoretic techniques; game tree evaluation; von Neumann's minimax theorem; [MR] pages 29-31.
  • November 9, 2016: Game-theoretic techniques; von Neumann's minimax theorem continued; Yao's technique; [MR] pages 32-34.
  • November 14, 2016: Game-theoretic techniques; Yao's technique continued; a lower bound for game tree evaluation; [MR] pages 34-37.
  • November 16, 2016: Game-theoretic techniques; a lower bound for game tree evaluation; randomness and non-uniformity; [MR] pages 37-39.
  • November 21, 2016: Game-theoretic techniques; randomness and non-uniformity; Moments and deviations; occupancy problems; [MR] pages 39-40 and 43-44.
  • November 28, 2016: Moments and deviations; occupancy problems; bucket sort; [MR] pages 44-45 [MU] pages 92-93.
  • November 30, 2016: Moments and deviations; bucket sort; inequalities by Markov and Chebyshev; [MU] pages 94 and 44-49.
  • December 5, 2016: Moments and deviations; median algorithm; [MU] pages 53-55 and [MR] pages 47-49.
  • December 12, 2016: Moments and deviations; median algorithm continued; two-point sampling; [MU] pages 55-57 and [MR] pages 51-52.
  • December 14, 2016: Moments and deviations; two-point sampling continued; coupon collector's problem; [MR] pages 52-53 and [MU] page 33.
  • December 19, 2016: Moments and deviations; coupon collector's problem continued; stable marriage problem; [MU] pages 50-55 and [MR] pages 53-54.
  • December 21, 2016: Moments and deviations; stable marriage problem continued; Chernoff bounds; moment generating functions; deriving Chernoff bounds; Poisson trials; [MR] page 56-57 and [MU] pages 61-64.
  • January 9, 2017: Chernoff bounds; deriving Cheroff bounds for Possoin trials; coin flips; parameter estimation; [MU] pages 64-68.
  • January 11, 2017: Chernoff bounds; parameter estimation continued; a better bound for a special case; set balancing; [MU] pages 68-72.
  • January 16, 2017: Chernoff bounds; packet routing on the hypercube; [MU] pages 72-74.
  • January 18, 2017: Chernoff bounds; packet routing on the hypercube; [MU] pages 75-76.
  • January 23, 2017: The probabilistic method; the basic counting argument; [MU] pages 126-128.
  • January 25, 2017: The probabilistic method; the expectation argument; [MU] pages 128-132.
  • January 30, 2017: The probabilistic method; sample and modify; Data structures; treaps; [MU] page 133 and [MR] 201-208.
  • Februar 1, 2017: Data structures; treaps; [MR] 201-208.
  • February 6, 2017: Data structures; treaps; [MR] 201-208.

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.

December 2017: Susanne Albers will give keynote address at the Graduation Day, Department of Computer Science at RWTH Aachen University.

ESA/ALGO 2019 will be organized by Susanne Albers and her group.

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.

Lehrstuhl für Theoretische Informatik
Prof. Dr. Susanne Albers

Boltzmannstr. 3
85748 Garching bei München

Tel +89.289.17706
Fax +89.289.17707

E-Mail
News