Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Theory of Combinatorial Algorithms
Prof. Emo Welzl and Prof. Bernd Gärtner
Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
Diese Seite wird fortlaufend ergänzt und ist noch nicht vollständig.
Bernd Gärtner, Robert Weismantel
Deutsch (Vorlesung, einige Übungsgruppen), English (some exercise classes). All teaching materials will be in English.
Dieses Material führt informell einige grundlegende mathematische Begriffe ein, die in der Vorlesung benutzt, dort aber nicht vertieft erklärt werden. Ausserdem gibt es Ihnen einen Einblick, wie die Mathematik "funktioniert", die dann auch Inhalt der Vorlesung sein wird. Teile dieses Materials werden in der Vorlesung Diskrete Mathematik formal eingeführt und vertieft.
Einige Studierende werden das Material aus dem Gynmnasium kennen, für andere wird es neu sein. Wir empfehlen Ihnen, das Material durchzusehen und die Teile genauer anzuschauen, mit denen Sie nicht vertraut sind. Die integrierten Übungsaufgaben helfen Ihnen dabei, Ihr Wissen zu überprüfen. Ihr Browser merkt sich den bisher gemachten Fortschritt.
Die fünf Reading Assignments sind keine Pflichtlektüre; Sie werden der Vorlesung auch ohne deren Bearbeitung folgen können. Es handelt sich um ein Angebot, mit dem wir versuchen möchten, Ihnen die Arbeits- und Denkweise der (universitären) Mathematik schon einmal näherzubringen. Wir hoffen aber, dass Sie auch Freude daran haben!
The exam will be available in both German or English, and it will be possible to answer in either language.
You are allowed to bring a 6-page summary to the exam, the official guidelines for this (copied from VVZ) are: "6 A4-Seiten Notizen oder 3 doppelseitige A4 Notizen (mit LaTeX oder Ähnlichem erfasste und gedruckte Notizen sind erlaubt; sie sollten ohne Lupe lesbar sein); ein Wörterbuch (Deutsch-Englisch oder andere Fremdsprache); kein Taschenrechner."
The course is structured in weeks, starting with Week 0.
Week 0 consists of a single lecture on Wednesday, September 17.
Week 1
consists of two lectures, the one on Friday September 19, and the one
on Wednesday September 24.
Week 2
consists of two lectures, the one on Friday September 26, and the lecture
on Wednesday October 01.
...
In particular, every week except Week 0
consists of exactly two lectures (Fri and Wed).
Apart from lectures, the course also consists of solving written assignments and solving auto-corrected quizzes in Moodle. Both are released weekly on Wednesdays (i.e. at the end of the course week). Solutions to written assignments are released with a delay of one week. Moreover, every assignment will have one (specially marked) exercise for which you can hand in a solution via Moodle and receive feedback from your TA.
The auto-corrected quizzes will be made available through Moodle. These quizzes can be attempted infinitely often. They are programmed such that you will get the same question with different numbers in every attempt.
During lectures, we will sometimes make use of 'Clicker'-questions. These are short multiple choice questions that you can answer using the ETH EduApp (available through app stores, but there is also a web-interface here). We recommend that you have access to this during lectures (on your smartphone or any other device) in order to take part.
Finally, there are 26 exercise sessions that take place every week (see further below). You can enroll into one of the sessions via mystudies. Note that the sessions differ in language, focus, time and place. If you have questions regarding the course content or the assignments, these sessions are the best place to ask them. The first set of exercise sessions take place already on Thu 18.09.25 and Fri 19.09.25, respectively.
In addition to the written assignments and the auto-graded quizzes, there will be one bonus task per week. By solving bonus tasks, you can collect a bonus for your final grade. The results from your 10 best bonus tasks will determine the grade bonus that you receive in the end. Every bonus task has the same weight, so it does not matter which 10 you solve. At most, you can get a bonus of +0.25 for your final grade. Every bonus task is either an auto-graded quiz or a written exercise that you will have to hand in. If the bonus task is an auto-graded quiz, you will be able to access it through Moodle. You will get 3 tries for the quiz and your best score will be counted. If the bonus task is a written exercise, you have to upload your handwritten (or Latex) solution via Moodle. A TA will then grade your solution.
You are required to solve the bonus quizzes (on Moodle) on your own. For the written bonus tasks, you need to hand-in your own independent solution (written by you), but you are allowed to discuss (verbally!) with other students that are taking the course as well.
Please note that bonus points from previous iterations of this course cannot be counted. So if you want to get a grade bonus for your exam, you need to do the bonus tasks of this year's iteration of the course.
The following table displays the content of the lecture organized by weeks. Every week is associated with two lectures (except Week 0), one assignment, solutions to the assignment, and a bonus task (except Week 0). In the table you also find the learning goals for every week, and you can see which sections of the lecture notes are taught in each week.
Lecture Notes: For the first half of the course, you can find the lecture notes here (version updated for HS25): part 1 . For the second half of the course, you can find the lecture notes here: part 2. Let us know if you find any mistake. Here is an up-to-date list of typos/mistakes in the lecture notes.
As mentioned under course structure, both assignments and auto-corrected quizzes, as well as the bonus task, will be released weekly on Wednesdays. Solutions to assignments will be released with a delay of one week.
Some of the material below is marked as "CS-Lens" (typically, these are slides). This material highlights connections of the course content with Computer Science. Material marked as "CS-Lens" is not relevant for the exam.
| Week | Dates | Sections | Lecture Plan | Notes / Slides | Assignment | Bonus | Learning Goals |
| 0 | Sep 17 | 1.1 | plan | slides tablet |
assignment solution |
quiz | basic vector operations (in Rm): add two vectors, multiply a vector with a scalar, compute linear combinations of two or more vectors; visualize and understand these operations geometrically |
| 1 | Sep 19 Sep 24 |
1.2 & 1.3 | plan | tablet |
assignment solution |
quiz | compute with vectors: scalar product, length, angles, Cauchy-Schwarz inequality, triangle inequality, hyperplanes, covectors; define linear independence of vectors in three different ways; work with the span of vectors |
| 2 | Sep 26 Oct 1 |
1.3 - 2.2 | plan |
tablet Animation |
assignment solution |
quiz | more on the span of vectors; matrices and linear combinations: matrix-vector multiplication, column space and rank, row space and transpose, nullspace, geometric interpretations |
| 3 | Oct 03 Oct 08 |
2.2 & 2.3 | plan | tablet |
assignment solution |
hand-in | linear transformations and linear functionals, the matrix of a linear transformation, matrix multiplication |
| 4 | Oct 10 Oct 15 |
2.3 & 2.4 | plan |
tablet Fast Fibonacci |
assignment solution |
quiz | matrix multiplication generalizes covector/vector/scalar multiplications; CR decomposition; invertible and inverse matrices: definition and basic properties |
| 5 | Oct 17 Oct 22 |
3.1 & 3.2 | plan |
tablet
Examples: nice, ugly, failing CS-Lens: Strassen algorithm |
assignment
solution |
quiz | systems of linear equations, the page rank algorithm; gauss elimination: back substiution, invariance under row operations, complexity |
| 6 | Oct 24 Oct 29 |
3.3 - 4.2 | plan | tablet Vector spaces Steinitz proof |
assignment
solution |
hand-in | gauss-jordan elimination; vector spaces: bases, steinitz exchange lemma, dimension |
| 7 | Oct 31 Nov 5 |
4.3 - 5.1 |
plan (Friday)
plan (Wednesday) |
tablet |
assignment
solution |
quiz | linear transformation between vector spaces; three fundamental subspaces: column space, row space, nullspace, their dimensions; all solutions of Ax=b; orthogonality of vectors and subspaces |
| 8 | Nov 7 Nov 12 |
5.1 - 6.1 |
plan (Friday)
plan (Wednesday) |
assignment
solution |
quiz | orthogonal decomposition of Rn; projections: one-dimensional case and in general, applications to least squares and data fitting | |
| 9 | Nov 14 Nov 19 |
6.2 & 6.4 |
plan (Friday)
plan (Wednesday) |
assignment
solution |
hand-in | orthogonality applied to systems of equations, a feasibility certificate; pseudoinverse: properties and relation to projections | |
| 10 | Nov 21 Nov 26 |
6.3 & 7.1 & 7.2 |
plan (Friday)
plan (partially Wednesday) |
assignment
solution |
quiz | orthonormal bases, orthogonal matrices; gram schmidt alogrithm, QR decomposition; determinants: definition and fundamental properties | |
| 11 | Nov 28 Dec 3 |
7.1 - 8.2 |
plan (partially Friday)
plan (partially Wednesday) |
assignment
|
quiz | more about determinants: key properties, cramer's rule; introduction to eigenvalues and eigenvectors | |
| 12 | Dec 5 Dec 10 |
8.2 - 9.1 |
plan (partially Friday)
plan (Wednesday) |
more on eigenvalues and eigenvectors: characteristic polynomials, links to the trace and determinant of a matrix; diagonalization of matrices | |||
There are 26 different exercise sessions that take place weekly. One of them is held online, all other exercise sessions take place in-person. Some of the sessions are held in German, others in English. Moreover, some of the sessions are marked as 'focus group'. Focus groups are intended for students who describe their own prior knowledge as below average. The focus group TAs therefore focus on the relevant basics and explain concepts as well as exercises in more detail. Apart from this, the focus groups cover the same content as the regular groups. Please sign up for one of the exercise sessions in mystudies.
| G-01 | German | Thu 8:15-10am | CAB G 56 | Valentin Gröner | ||
| G-02 | German | Thu 8:15-10am | CHN C 14 | Annika Guhl | ||
| G-03 | German | Thu 8:15-10am | CHN D 42 | Silvan Bolt | ||
| G-04 | German | Thu 8:15-10am | CHN D 46 | Simon Krause | ||
| G-05 | German | Focus Group | Thu 8:15-10am | CLA E 4 | Simon-Philipp Merz | |
| G-06 | German | Focus Group | Thu 8:15-10am | HG F 26.5 | Tae Kim | |
| G-07 | English | Thu 8:15-10am | IFW A 32.1 | Clemens Sageder | ||
| G-09 | German | Thu 8:15-10am | RZ F 21 | Moritz Schwalm | ||
| G-10 | German | Thu 8:15-10am | HG E 22 | Clemens Steinwendner | ||
| G-11 | English/French | Focus Group | Thu 8:15-10am | ML F 38 | Theophile Thiery | |
| G-12 | English | Thu 8:15-10am | ML H 41.1 | Stanislav Kostov | ||
| G-13 | German | Focus Group | Thu 4:15-6pm | NO C 6 | Hannah Schwede | |
| G-14 | English | Thu 4:15-6pm | IFW A 34 | Jing Ren | ||
| G-15 | English | Focus Group | Thu 4:15-6pm | CHN D 42 | Mohamed-Hicham Leghettas | |
| G-16 | German | Thu 4:15-6pm | LFW E 13 | Niklas Weßbecher | ||
| G-17 | English | Thu 4:14-6pm | ML J 34.3 | Metehan Kilic | ||
| G-18 | English | Thu 4:15-6pm | ML J 37.1 | Boris Gachevski | ||
| G-19 | English | Thu 4:15-6pm | CAB G 56 | Manuel di Sabatino | ||
| G-20 | English | Fri 2:15-4pm | IFW A 34 | Shuhao Li | ||
| G-21 | German | Fri 2:15-4pm | CHN D 42 | Julian Weide | ||
| G-22 | German | Fri 2:15-4pm | ETZ E 9 | Benjamin Gruzman | ||
| G-23 | English | Fri 2:15-4pm | LFW C 4 | Aviv Segall | ||
| G-25 | German | Focus Group | Fri 2:15-4pm | IFW C 31 | Paul Cremer | |
| G-26 | English | Fri 2-4pm | online | Saleh Ashkboos | ||
