# Randomized Algorithms and Probabilistic Analysis of Algorithms

## News

You can inspect your final exam by going to Philip's office (whenever Philip is around; feel free to contact Philip first to ensure this)

## Basic Information

Lectures: Wednesdays, 14:00-16:00, E 1 4 Room 0 24 Philip Wellnitz Oct 26 Thursdays (every other week), 16:00-18:00, E 1 4 Room 0 24 Baris Can Esmer Nov 3 5 Feb 27, 14:00 to 16:00, E1 4 Room 0 24 Basic knowledge in algorithms and stochastics

## 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 sorting, and network and graph problems. We will also briefly cover sublinear algorithms.

## Schedule

LectureTopicReference (see below)
October 26Introduction, Course Overview
Verifying Matrix Multiplication, Randomized Min Cut
MU Section 1.3, 1.5
MR Section 10.2, [KS93]
November 2Fair and Biased Coins
Probabilistic Analysis of Quicksort
MU Section 2.4
MU Section 2.5
November 9Collecting Coupons
Randomized Median
MU Section 3.1, 3.2, 3.3
MU Section 3.5
November 16Chernoff Bounds
Balls and Bins, Poisson Approximation (1)
MU Section 4.1, 4.2
MU Section 5.2, 5.3
November 23Poisson Approximation (2)
Bloom Filter
MU Section 5.4
MU Section 5.5
November 30Random Graph Models, Randomized Hamiltonian CycleMU Section 5.6
December 7Markov Chains, Randomized 2SAT (1)MU Section 7.1, 7.2, 7.3
December 14Random Walks in Graphs, Randomized 2SAT (2)
Approximate Sampling and Approximate Counting
MU Section 7.4, 7.1.1
MU Section 11.1, 11.3, [JVV86]
(December 21)
(January 4)
Exercise Sheet 5 (Probabilistic Method)MU Section 6.1, 6.2
MU Section 6.4, 6.7
January 11Markov Chain Monte Carlo
Coupling of Markov Chains
MU Section 11.4
MU Section 12.1, 12.2
January 18A Gentle Introduction to MartingalesMU Section 13
More background: [W91], Part B
January 25Property Testing (1)
Testing Majority; testing Monotonicity
[G17] Section 1.2, 1.3
[G17] Section 4.2
February 1Property Testing (2)
Testing Bipartiteness, upper and lower bounds
[G17] Section 8.1, 8.3
February 8Special Lecture: Ariel Kulik
Special Lecture: Tomasz Kociumaka
Special Lecture: Danupon Nanongkai

[slides]
[slides]

## Exam

There will be a written exam in room 0 24, on Feb 27, 2023, 14:00 to 16:00. You are required to get 50% of the points in the exercises to take the exam. You also have to register ≥ 1 week in advance in the system relevant to your course of study.

The exam will take 120 minutes. You are allowed to use a (double-sided) A4 cheat sheet (handwritten).

## Exercise Sets

Exercise SetDue dateTutorial Session
Exercise Set 1November 9November 17
Exercise Set 2November 23December 1
Exercise Set 3December 7January 12
Exercise Set 4 / 5January 11January 19
Exercise Set 6January 25Febuary 2

## Literature

(Additional literature for specific lectures will be added after the corresponding lectures.)