Department of Computer Science | Institute of Theoretical Computer Science

CADMO - Center for Algorithms, Discrete Mathematics and Optimization

Randomized Algorithms and Probabilistic Methods — Autumn 2022

This page is the official website of the course Randomized Algorithms and Probabilistic Methods (252-0417-00L), or RandAlg for short. It should be your main source of information on the lecture. You can find the lecture notes, the exercises, etc. Any important information relative to the lecture will also be posted here.

Lecturer

Prof. Dr. Angelika Steger

Teaching Assistants

Yassir Akram, Marc Kaufmann, Charlotte Knierim, Maxime Larcher, Dr. Anders Martinsson, Patryk Morawski, Ulysse Schaller and Dr. Raphael Steiner.

If you have a general question related to the organisation of the course, please contact the Head TA Maxime Larcher

Time and Place

Lecture: Wednesday 12:15 - 13:00 in CAB G 11 and Thursday 08:15 - 10:00 in CAB G 61.

Please note that the lectures will be neither streamed nor recorded. As the course progresses, we will publish the list of topics that have been covered (see below). If you missed one of the lectures, please refer to that list and read the corresponding chapters.

Exercise Class: You can attend one of the three following exercise classes:

Exam: The exam will take place on Saturday 17.12.2022 from 10:00 to 13:00 in rooms HG F 1 and HG F 7. Please go to room HG F 1 if you family name starts with one of the letters A-K, and go to room HG F 7 if it starts with one of the letters L-Z.

Participants

Students of Computer Science or Mathematics in the 5th semester or later. Knowledge of topics covered in the lecture "Algorithms, Probability, and Computing" is not required; both courses can be attended in parallel.

Exam/Grades

Your final grade will be calculated as the the weighted average of:

Following the D-INFK guidelines for doctoral studies, PhD students get credit points according to the same rules that apply for Bachelor or Master students. That is, with a final grade of at least 4 (calculated as explained above) you will receive 10 ECTS, and 0 ECTS otherwise.

We provide the exams of previous years HS16, HS17, HS18 so you can have an idea of what we expect. One of the theorems was removed from the Lecture in 2018, so you may not be able to solve Exercise 3 of 2017. We will not provide solutions for those exercises.

Lecture Notes

The lecture notes can be found here: Script 19.09.2022. The lecture notes are updated occasionally and we will let you know whenever a new version is available.

Exercises

The exercise classes are an integral part of the course. Thus, we strongly recommend you to attend them regularly and solve the weekly exercise sheets.

Exercise Sheet 1

Exercise Sheet 1 Solutions

Exercise Sheet 2

Exercise Sheet 2 Solutions

Exercise Sheet 3

Exercise Sheet 3 Solutions

Practice Graded Homework 1 (Guidelines for Graded Homeworks)

Practice Homework Solutions (Grading Scheme)

Exercise Sheet 4

Exercise Sheet 4 Solutions

Exercise Sheet 5

Exercise Sheet 5 Solutions

Graded Homework 2

Graded Homework 2 Solutions

Exercise Sheet 6

Exercise Sheet 6 Solutions

Exercise Sheet 7

Exercise Sheet 7 Solutions

Exercise Sheet 8

Exercise Sheet 8 Solutions

Graded Homework 3

Graded Homework 3 Solutions

Exercise Sheet 9

Exercise Sheet 9 Solutions

Exercise Sheet 10

Exercise Sheet 10 Solutions

Handouts

This pdf contains a short introduction to big-oh notation, asymptotics and it also contains some useful inequalities.

We provide the following LaTeX template which you can use and modify when submitting homework and graded homework. To save the LaTex template, you need to right-click on the link and the "save the target" wherever you want to save it. Just clicking on the link will not be of much use, as you will just see the squeezed LaTeX code.

Topics Covered in Class

As the semester progresses, we will publish here a list of the topics which have been covered.

Lecture 1 (21.09):
- The probabilistic method (Section 1.2 of the Script).
- Ramsey numbers (Section 1.3).
- Satisfiability of Boolean Formulas (Section 1.4) — to be continued on 22.09.
Lecture 2 (22.09):
- Satisfiability of Boolean Formulas (Section 1.4) — finished.
- Linearity of Expectation (Chapter 2).
- Independent Sets in Graphs (Section 2.1).
- The Coupon Collector Problem (Section 2.2).
- An Approximation Algorithm for Max-3-Sat (Section 2.3) — to be continued on 28.09.
- Long Paths in Graphs (Section 1.5) will not be covered, but we invite you to read it.
Lecture 3 (28.09):
- An Approximation Algorithm for Max-3-Sat (Section 2.3) — finished.
Lecture 4 (29.09):
- Calculating the Median (Section 3.2).
- First & Second Moment Method (Chapter 4).
- Markov and Chebyshev inequalities will not be proved in class, but will be used many times. We invite you to read the corresponding material (Chapter 3).
- The Coupon Collector Problem: Concentration (Section 3.1) will not be covered, but we invite you to read it.
Lecture 5 (05.10):
- Threshold Phenomena in Random Graphs (Chapter 4.1) — Triangles in Random Graphs.
Lecture 6 (06.10):
- Chernoff Bounds (Chapter 5)
- Target Shooting (Section 5.1) was mentioned but not covered.
- Routing on the Hypercube (Section 5.2) — To be continued on 12.10.
Lecture 7 (12.10)
- Routing on the Hypercube (Section 5.2) — Finished.
Lecture 8 (13.10)
- Negative Correlation (Chapter 6).
- Chernoff Bound with Negative Association (Theorem 6.4).
- Tools for Proving Negative Association (Lemmata 6.5-6.7).
- Load Distribution in Networks (Section 6.1) — To be continued on 19.10.
Lecture 9 (19.10)
- Power of Two Choices (Section 6.1.1, without proofs) — Finished.
Lecture 10 (20.10)
- Azuma's Inequality (Chapter 7).
Lecture 11 (26.10)
- Janson's Inequality (Chapter 7).
Lecture 12 (27.10)
- Talagrand's Inequality (Chapter 8).
Lecture 13 (02.11)
- Introduction to Markov Chains (Chapter 9).
Lecture 14 (03.11)
- Drift Theorems (Chapter 9), to be continued on 09.11.
Lecture 15 (09.11)
- Recap Additive Drift Theorems.
- Multiplicative Drift Theorem (Theorem 9.12) — proof to be concluded on 10.11.
Lecture 16 (10.11)
- Multiplicative Drift Theorem (Theorem 9.12) — finished.
- Variable Drift Theorem.
- 3-SAT: Schöning's Algorithm (Section 9.3).
Lecture 17 (16.11)
- Stationary Distribution (Chapter 10).
- Definition of Ergodicity.
- Fundamental Theorem of Ergodic Markov Chains.
Lecture 18 (17.11)
- Rapidly Mixing Chains (Section 10.1).
- Characterisation by Flows up to Example 1 (Section 10.1.1).
Lecture 19 (23.11)
- Characterisation by Coupling (Section 10.1.2) — To be continued on 24.11.
Lecture 20 (24.11)
- Characterisation by Coupling (Section 10.1.2) — Finished
- Generating and Counting k-colorings (Section 10.3).
Lecture 21 (30.11)
- Generating Functions (Chapter 11) — To be continued on 01.12.
Lecture 22 (01.12)
- Generating Functions (Chapter 11) — Finished.
Every topic addressed after this point is non-examinable.
Lecture 23 (07.12)
- How to get Rich? (Section 12.1).
Lecture 24 (08.12)
- Bandits.

Outline of the Course

The lecture will cover the following topics. Small changes may be brought to this list as the semester progresses.

Introduction

Linearity of expectation

Markov and Chebyshev inequalities

First and second moment method

Chernoff bounds

Negative Correlation

Janson, Azuma and Talagrand inequalities

Markov chains

Outlook (if time permits)

Literature