Department of Computer Science | Institute of Theoretical Computer Science

CADMO - Center for Algorithms, Discrete Mathematics and Optimization

Randomized Algorithms and Probabilistic Methods — Autumn 2021

This website 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 also find the lecture notes, the exercises, etc. Any important information relative to the lecture will be posted here.

Lecturer

Prof. Dr. Angelika Steger

Assistants

Yassir Akram, Frederik Benzing, Charlotte Knierim, Maxime Larcher, Lukas Lötscher, Dr. Anders Martinsson, Dr. Raphael Steiner and Nicolas Zucchet

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

Time and Place

Lecture: Wednesday 8:15 - 9:00 in ML D 28 and Thursday 16:15 - 18:00 in ML D 28.

For those of you who cannot attend physically, the lectures will be streamed.

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

Exam: Saturday 18.12.2021, 10:00-13:00.

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

We will publish exercises here.

Exercise Sheet 1

Exercise Sheet 1 Solutions

Exercise Sheet 2

Exercise Sheet 2 Solutions

Exercise Sheet 3

Exercise Sheet 3 Solutions

Graded Homework 1 (Guidelines for GHW1)

Graded Homework 1 Solutions

Graded Homework 1 — Common Mistakes

Exercise Sheet 4

Exercise Sheet 4 Solutions

Exercise Sheet 5

Exercise Sheet 5 Solutions

Exercise Sheet 6

Exercise Sheet 6 Solutions

Graded Homework 2

Graded Homework 2 Solutions

Graded Homework 2 — Common Mistakes

Exercise Sheet 7

Exercise Sheet 7 Solutions

Exercise Sheet 8

Exercise Sheet 8 Solutions

Exercise Sheet 9

Exercise Sheet 9 Solutions

Graded Homework 3

Exercise Sheet 10

Exercise Sheet 10 Solutions

Exercise Sheet 11

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 (22.09):
- The probabilistic method (Section 1.2 of the Script).
- Ramsey numbers (Section 1.3).
Lecture 2 (23.09):
- Satisfiability of Boolean Formulas (Section 1.4).
- Linearity of Expectation (Chapter 2).
- The Coupon Collector Problem (Section 2.2).
- An Approximation Algorithm for Max-3-Sat (Section 2.3).
- Long Paths in Graphs (Section 1.5) will not be covered, but we invite you to read it.
- Independent Sets in Graphs (Section 2.1) will not be covered, but we invite you to read it.
Lecture 3 (29.09):
- Calculating the Median (Section 3.2) — To be continued on 30.09.
- 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).
Lecture 4 (30.09):
- Calculating the Median (Section 3.2) — Finished.
- First & Second Moment Method (Chapter 4).
- Threshold Phenomena in Random Graphs (Chapter 4.1) — Isolated Vertices in Random Graphs.
Lecture 5 (06.10):
- Threshold Phenomena in Random Graphs (Chapter 4.1) — Triangles in Random Graphs.
Lecture 6 (07.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 13.10.
Lecture 7 (13.10)
- Routing on the Hypercube (Section 5.2) — Finished.
Lecture 8 (14.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 20.10.
Lecture 9 (20.10)
- Load Distribution in Networks (Section 6.1) — Finished.
- Power of Two Choices (Section 6.1.1) — To be continued on 21.10.
Lecture 10 (21.10)
- Power of Two Choices (Section 6.1.1) — Finished.
Lecture 11 (27.10)
- Azuma's Inequality (Chapter 7).
- Vertex- and edge-exposure (Section 7.1).
Lecture 12 (28.10)
- Janson's Inequlity (Chapter 7).
- Wilf's Algorithm (Section 7.2).
- Longest Increasing Subsequence (Section 8.1) — To be continued on 03.11.
Lecture 13 (03.11)
- Talagrand's Inequality (Chapter 8).
- Longest Increasing Subsequence (Section 8.1) — Finished.
Lecture 14 (04.11)
- Markov Chains (Chapter 9).
- Gambler's Ruin (Section 9.1).
- 3-SAT Approximaton (Section 9.3).
Lecture 15 (10.11)
- Drift Theorems and Random Decline (Section 9.2).
- Additive Drift Theorems (Theorems 9.9 and 9.10).
- Multiplicative Drift Theorem (Theorem 9.11) — To be continued on 11.11.
Lecture 16 (11.11)
- Multiplicative Drift Theorem (Theorem 9.11) — Finished.
- Drift and Concentration Bounds (Section 9.2).
- Example with drift towards infinity, but state 0 reached in small expected time (Section 9.2).
Lecture 17 (17.11)
- Stationary Distribution (Chapter 10).
- Definition of ergodicity.
- Fundamental Theorem of Ergodic Markov Chains.
- All definitions and results up to Lemma 10.10.
Lecture 18 (18.11)
- Rapidly Mixing Chains (Section 10.1).
- Characterisation by Flow (Section 10.1.1).
Lecture 19 (24.11)
- Characterisation by Coupling (Section 10.1.2) — To be continued on 25.11.
Lecture 20 (25.11)
- Characterisation by Coupling (Section 10.1.2) — Finished
- Generating and Counting k-colorings (Section 10.3).
Lecture 21 (01.12)
- Generating Functions (Chapter 11) — To be continued on 02.12.
Lecture 22 (02.12)
- Generating Functions (Chapter 11) — Finished.
Every topic addressed after this point is non-examinable.
- How to get Rich? (Section 12.1).

Preliminary Topics (subject to small changes)

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