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:

• Tuesday, 14:15 - 16:00 in HG D 1.2;
• Tuesday, 16:15 - 18:00 in HG D 1.2.

Exam: Saturday 18.12.2021, 10:00-13:00. The exam will happen in rooms HG F 1 and HG F 7. If you are registered for the exam, then you have received an email explaining in which room you should go.

Repetition Exam: Saturday 26.02.2022, 10:00-13:00. The exam will happen in room HG E 1.1.

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:

• 70% final written exam. Duration: 3 hours. Open book exam - you are allowed to consult any books, handouts, and personal notes. The use of electronic devices is not allowed. We will provide practice exams as the semester progresses.
• 30% graded homework. In week 4, 7 and 10 of the term (roughly) we will hand out specially marked exercise sheets whose solutions (typeset in LaTeX) will be due two weeks later. These solutions will be graded; the grades will each account for 10% of your final grade. You are welcome to discuss these exercises with your colleagues, but we expect you to hand in your own, individual writeup.

  We understand that it is possible that some of you fall sick and are unable to fully solve all exercises of the graded homeworks. If you bring a doctor's note stating that you were unable to work during the last days before the deadline, then we can offer the following options:

  • 1-2 days incapacity: no arrangement.
  • 3-4 days incapacity: you may choose one exercise that we will not grade. All other exercises will be graded and your total number of points will be scaled.
  • 5 or more days: you do not have to submit anything. The exam will count an additional 10% towards your final grade.
  If you are sick for more than 7 out of the 14 days given to you to solve a graded homework, then the last applies: you do not have to submit and the exam will count an additional 10% towards your final grade.

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

Graded Homework 3 Solutions

Exercise Sheet 10

Exercise Sheet 10 Solutions

Exercise Sheet 11

Exercise Sheet 11 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 (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).
Lecture 23 (08.12) - The Online Matching Problem (Section 12.5).
Lecture 24 (09.12) - The Entropy Intuition (Section 12.9).
Lecture 25 (15.12) - The Chromatic Number of Triangle-Free Graphs (Section 12.7).
Lecture 26 (15.12) - Smallest Enclosing Circle (Section 12.2). - The Ski Rental Problem (Section 12.4).
NO LECTURE OR EXERCISE CLASSES IN THE LAST WEEK OF THE SEMESTER.

Preliminary Topics (subject to small changes)

Introduction

• Randomized algorithms (Longest Path, SAT)
• Probabilistic methods (Random Graphs without induced cliques/independent sets of size k)

Linearity of expectation

• Coupon Collector problem
• 7/8-approximation algorithm for Max-3-SAT

Markov and Chebyshev inequalities

• Random graphs
• Calculating the median in linear time

First and second moment method

• Threshold phenomena in random graphs

Chernoff bounds

• Target shooting
• Routing in the hypercube

Negative Correlation

• Load balancing in networks ("balls and bins")

Janson, Azuma and Talagrand inequalities

• Subgraphs in random graphs
• Wilf's algorithm (3-coloring of graphs)
• longest increasing subsecquence

Markov chains

• Gambler's Ruin problems
• Drift Analysis
• Algorithm for 3-SAT
• Couplings of Markov chains

Outlook (if time permits)

• Generating functions
• Randomized rounding
• Average case analysis
• ...

Literature

• The Probabilistic Method, 3rd Edition, Noga Alon and Joel H. Spencer, John Wiley & Sons (2008)
• Randomized Algorithms, Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press (2000)
• Probability and Computing, Michael Mitzenmacher and Eli Upfal, Cambridge University Press (2005)