Randomized Algorithms and Probabilistic Analysis of Algorithms
Advanced Course, 2+1
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 |
|---|---|
| Lecturer: | Philip Wellnitz |
| First lecture: | Oct 26 |
| Tutorials: | Thursdays (every other week), 16:00-18:00, E 1 4 Room 0 24 |
| Assistant: | Baris Can Esmer |
| First tutorial: | Nov 3 |
| Credits: | 5 |
| Exam: | Feb 27, 14:00 to 16:00, E1 4 Room 0 24 |
| Prerequisites: | 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
| Lecture | Topic | Reference (see below) |
|---|---|---|
| October 26 | Introduction, Course Overview Verifying Matrix Multiplication, Randomized Min Cut | MU Section 1.3, 1.5 MR Section 10.2, [KS93] |
| November 2 | Fair and Biased Coins Probabilistic Analysis of Quicksort | MU Section 2.4 MU Section 2.5 |
| November 9 | Collecting Coupons Randomized Median | MU Section 3.1, 3.2, 3.3 MU Section 3.5 |
| November 16 | Chernoff Bounds Balls and Bins, Poisson Approximation (1) | MU Section 4.1, 4.2 MU Section 5.2, 5.3 |
| November 23 | Poisson Approximation (2) Bloom Filter | MU Section 5.4 MU Section 5.5 |
| November 30 | Random Graph Models, Randomized Hamiltonian Cycle | MU Section 5.6 |
| December 7 | Markov Chains, Randomized 2SAT (1) | MU Section 7.1, 7.2, 7.3 |
| December 14 | Random 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 11 | Markov Chain Monte Carlo Coupling of Markov Chains | MU Section 11.4 MU Section 12.1, 12.2 |
| January 18 | A Gentle Introduction to Martingales | MU Section 13 More background: [W91], Part B |
| January 25 | Property Testing (1) Testing Majority; testing Monotonicity | [G17] Section 1.2, 1.3 [G17] Section 4.2 |
| February 1 | Property Testing (2) Testing Bipartiteness, upper and lower bounds | [G17] Section 8.1, 8.3 |
| February 8 | Special 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 Set | Due date | Tutorial Session |
|---|---|---|
| Exercise Set 1 | November 9 | November 17 |
| Exercise Set 2 | November 23 | December 1 |
| Exercise Set 3 | December 7 | January 12 |
| Exercise Set 4 / 5 | January 11 | January 19 |
| Exercise Set 6 | January 25 | Febuary 2 |
Literature
- [MU] Probability and Computing by Mitzenmacher/Upfal (second edition)
- [MR] Randomized Algorithms by Motwani/Raghavan
- [KS93] An Õ(n2) algorithm for minimum cuts by Karger/Stein, STOC'93
- [JVV86] Random generation of combinatorial structures from a uniform distribution by Jerrum/Valiant/Vazirani, TCS'86
- [W91] Probability with Martingales by David Williams
- [G17] Introduction to Property Testing by Oded Goldreich
(Additional literature for specific lectures will be added after the corresponding lectures.)