Department of Computer Science | Institute of Theoretical Computer Science
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.
Lecture: Wednesday 8:15 - 9:00 in ML D 28 and Thursday 16:15 - 18:00 in ML D 28.
Exercise Class: You can attend one of the two following exercise classes:
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.
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:
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 15.12.21. 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.
We will publish exercises here.
Graded Homework 1 (Guidelines for GHW1)
Graded Homework 1 — Common Mistakes
Graded Homework 2 — Common Mistakes
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 (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. |
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)