# 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.