# Randomized Algorithms and Probabilistic Analysis of Algorithms

## Advanced Course, 2+1

## Basic Information

Lectures: | Monday, 16:15 - 18:00, E1 4 024 |
---|---|

Lecturers: | Thomas Kesselheim and Kurt Mehlhorn |

First lecture: | April 25, 2015 |

Tutorials: | Wednesday, 10:00 - 12:00, E 1 4 023, biweekly |

Assistant: | Pavel Kolev |

First tutorial: | TBA |

Credits: | 5 |

Prerequisites: | Basic knowledge in algorithms and stochastic |

## Description

Randomization is a helpful tool when designing algorithms. When there are many possible options many of which are good, it is a lot easier to have the algorithm flip a coin rather than describing an appropriate deterministic rule. Also, worst-case effects might be avoided this way. For these reasons, many practical algorithms use randomization, such as for example primality testing in cryptography. In other case, the input to an algorithm itself can already be assumed to be probabilistic. For example, sorting algorithms often have a bad worst-case running time only due to a single instance, which is very unlikely to occur in a real input. In these cases it make sense to analyze algorithms under probabilistic input models.

In this course, we will introduce you to the foundations of randomized algorithms and probabilistic analysis of algorithms. We will cover different combinatorial settings such as load balancing, sorting, and network and graph problems.

## Exam

There will be oral exams after the lecture period by individual appointment. You are required to get 50 % of the points in the exercises to take the exam.

## Lecture Notes and Materials

July 18, Yao's Principle and the Secretary Problem

June 27 and July 4, Satisfiability, Rapid Mixing

June 13, Introduction to Smoothed Analysis (typos fixed June 21)

June 6, The Probabilistic Method(Slides), Video Lecture (160 MB)

May 30, Load Balancing and Chernoff Bounds, Chernoff Bounds Cheat Sheet

May 23, Bloom Filters and Locality-Sensitive Hashing

May 9, Quicksort and Randomized Incremental Constructions

May 2: Min Cut, Fast Cut, Polynomial Identities

April 25: Contention Resolution

Coupon Collector: ODS, XLS

Contention Resolution n=10: ODS, XLS

Contention Resolution n=25: ODS, XLS

Basics in Probability Theory: You should know everything in this section except for Chernoff bounds and everything that follows.

## Exercise Sets

Exercise Set | Due date | Tutorial Session | |
---|---|---|---|

Exercise Set 1 | May 9 | May 11 | |

Exercise Set 2 | May 30 | June 1 | |

Exercise Set 3 | June 13 | June 15 | |

Exercise Set 4 | June 27 | June 29 | |

Exercise Set 5 | July 11 | July 13 | |

Exercise Set 6 | July 25 | July 27 |

# E-Mail Announcements

## Literature

- Randomized Algorithms by Motwani/Raghavan
- Probability and Computing by Mitzenmacher/Upfal
- Chapter 13 in Algorithm Design by Kleinberg/Tardos available online (see sample chapters)