Department of Computer Science | Institute of Theoretical Computer Science
Department of Computer Science | Institute of Theoretical Computer Science
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
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.
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.
Your final grade will be calculated as the the weighted average of:
Note that contrary to previous years, there will only be two graded homeworks. Around week 4, we will post a practice homework to give you an idea of what to expect for the real graded homeworks. You are encouraged to hand in your solution (at least a partial one) and we will provide feedback, but you will not receive a grade for this practice homework. We will also provide an official solution.
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:
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.
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.
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.
Practice Graded Homework 1 (Guidelines for Graded Homeworks)
Practice Homework Solutions (Grading Scheme)
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.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. |
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)