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 wir fortlaufend ergänzt und ist noch nicht vollständig.
Bernd Gärtner, Afonso Bandeira
Deutsch (Bernd Gärtner, einige Übungsgruppen), English (Afonso Bandeira, 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. More details regarding this will follow.
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."
A mock exam will be made available to the students at the end of the semester.
Note that we will continue to update you with new information regarding the exam. If you have any questions regarding the exam that need to be answered now, please contact Sebastian (preferably via Moodle).
The course is structured in weeks starting with Week 0.
Week 0 consists of a single lecture on Wednesday, September 20.
Week 1
consists of two lectures, the one on Friday September 22, and the one
on Wednesday September 27.
Week 2
consists of two lectures, the one on Friday September 29, and the lecture
on Wednesday October 04.
...
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. 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. Note that these hand-in exercises are NOT graded and do not count towards your bonus.
The auto-corrected quizzes will be made available through Moodle. Every week there is one bonusquiz and many 'normal' quizzes. By solving bonusquizzes you can collect a bonus for your final grade. The results from your 10 best bonusquizzes will determine the grade bonus that you receive in the end. At most, you can get a bonus of +0.25 for your final grade. You will get 3 tries on every bonusquiz (the best one counts). You are required to solve the bonusquizzes on your own!
Normal 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. We will start using Clicker-questions on September 22 (first Friday lecture).
Finally, there are 24 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 21.09.23 and Fri 22.09.23, respectively.
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 bonusquiz. 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. For the first half of the course, you can find the lecture notes here: part 1 . For the second half of the course, you can find the lecture notes here: part 2. The notes for the second part will be updated regularly.
As mentioned under course structure, both assignments and auto-corrected quizzes including the bonusquiz 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 | Notes / Slides | Assignment | Solution | Bonus | Learning Goals |
| 0 | Sep 20 | 1.1 | Slides Notes |
Assignment 0 | Solution 0 | Bonus 0 | basic vector operations (in R^n): 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 22 Sep 27 | 1.2 & 1.3 | Notes Slides Notes |
Assignment 1 | Solution 1 | Bonus 1 | compute with vectors: scalar product, length, cosine formula, Cauchy-Schwarz inequality, triangle inequality, perpendicular vectors, hyperplanes; compute with matrices: matrix-vector multiplication, column space, row space, rank; define linear independence of vectors in three different ways |
| 2 | Sep 29 Oct 04 | 1.4 & 2.1 | Notes Notes CS-Lens (associativity) |
Assignment 2 | Solution 2 | Bonus 2 | perform matrix multiplication, including matrix- vector, vector-matrix, scalar and outer product, distributivity, associativity; explain the CR decomposition; do elimination and back substitution on systems of linear equations; explain when and why this works or fails |
| 3 | Oct 06 Oct 11 | 2.2 & 2.3 |
Notes Notes CS-Lens (Strassen) |
Assignment 3 | Solution 3 | Bonus 3 | define the inverse of a matrix; compute inverses of 2 × 2 matrices; characterize when the inverse exists (The Inverse Theorem); invert a product of matrices; count operations during elimination and back substitution; derive and explain the LU factorization from elimination |
| 4 | Oct 13 Oct 18 |
2.4 & 3.1 |
Notes Notes |
Assignment 4 | Solution 4 | Bonus 4 | define and work with permutation matrices, transposed and symmetric matrices; derive and explain the PA=LU factorization and the symmetric LU factorization; explain the concept of a vector space; give an example that is not R^n; define and identify subspaces; explain when vectors span a subspace / form a basis of it |
| 5 | Oct 20 Oct 25 |
3.2 & 3.3 |
Notes Notes CS-Lens (vectors) |
Assignment 5 | Solution 5 | Bonus 5 | define the nullspace of a matrix; explain reduced row echelon form (rref); compute a basis for the nullspace of a matrix in rref; compute the rref of a given m x n matrix A; explain why it equals R in A=CR; solve Ax=b by elimination to rref; read off all solutions; count the number of solutions |
| 6 | Oct 27 Nov 01 |
3.4 & 3.5 |
Notes Notes |
Assignment 6 | Solution 6 | Bonus 6 | prove that every vector of a subspace is a unique combination of basis vectors, and that every basis has the same number of vectors; define the dimension of a subspace; compute bases for given subspaces; define the four fundamental subspaces of a matrix: column space, row space, nullspace, left nullspace; compute their dimensions, depending on shape and rank of the matrix |
| 7 | Nov 03 Nov 08 |
4.1 & 4.2 |
Typed notes Notes Handwritten notes Slides (Intro) |
Assignment 7 | Solution 7 | Bonus 7 |
define orthogonal subspaces; prove that nullspace and row space of a matrix are orthogonal; argue about dimensions of two orthogonal subspaces; define orthogonal complement and explain its three different characterizations; explain the big picture; Define Projection, Derive formula for Projection on a subspace, Compute the Projection Matrix. Show that when A has independent columns, A^TA is invertible and symmetric. |
| 8 | Nov 10 Nov 15 |
4.3 & 4.4 |
Typed notes Handwritten notes CS Lens (kernel method) Handwritten notes |
Assignment 8 | Solution 8 | Bonus 8 |
Define Least Squares solution, derive Normal equations, compute a least squares solution. Use Least Squares to fit a line to points (linear regression). rank(A^TA)=rank(A). Orthogonal vectors, Orthonormal vectors. Orthogonal Matrices. Orthogonal matrices preserve norm and inner-product. Projections with orthonormal bases. Build an orthonormal basis with Gram-Schmidt (and show correctness of Gram-Schmidt). |
| 9 | Nov 17 Nov 22 |
4.5 |
Typed notes Handwritten notes CS Lens (Networks and LA) Handwritten notes |
Assignment 9 | Solution 9 | Bonus 9 |
QR decomposition. Projections, and least squares, with QR decomposition. Pseudo-inverse, definition and properties. Pseudo-inverse and least squares for full column rank matrices. Pseudo-inverse and minimum norm solution for full row rank matrices. Linear transformations, Visualizing linear transformations in 2d. Properties of Linear Transformations. Matrix representation of linear transformations. |
| 10 | Nov 24 Nov 27 |
5.0 & 5.1 |
Typed notes Handwritten notes Handwritten notes |
Assignment 10 | Solution 10 | Bonus 10 | Linear trasformatios, examples of transformations that are linear, examples of transformations that are not linear. Determinant and its properties, definition via permutations, connection to matrix inverse, co-factors and the determinant, Cramer's rule, determinant of orthogonal matrices, determinant of triangular matrices, arguing about the determinant. |
| 11 | Dec 01 Dec 06 |
6.0 & 6.1 |
Typed notes Handwritten notes Handwritten notes CS Lens (PageRank) |
Assignment 11 | Solution 11 | Bonus 11 | Complex numbers, calculations with complex numbers, conversion between cartesian form and polar form, Euler's formula. Fundamental theorem of algebra, roots of polynomials. Complex-valued vectors and matrices. Eigenvalues and eigenvectors, characteristic polynomial, algebraic multiplicity, finding eigenvalues and eigenvectors, properties of eigenvalues and eigenvectors. Linear independence of eigenvectors corresponding to distinct eigenvalues. Determinant, trace, and connection to eigenvalues. |
| 12 | Dec 08 Dec 13 |
6.1 - 6.3 |
Typed notes
Handwritten notes Handwritten notes |
Assignment 12 | Solution 12 | Bonus 12 | Eigenvalues an eigenvectors of rotations and other linear transformations. Eigenvalues and eigenvectors of orthogonal matrices. Eigenvalues and eigenvectors of diagonal matrices. Eigenvalues and eigenvectors of projection matrices. Repeated eigenvalues and geometric multiplicity. Linear independence of eigenvectors, complete sets of real eigenvectors. Change of basis, change of basis matrix. Diagonalization, diagonalizable matrices. Similar matrices, eigenvalues of similar matrices. Spectral theorem: eigenvalues and eigenvectors of symmetric matrices. |
| 13 | Dec 15 Dec 20 |
6.3 & 7.1 - 7.2 |
Typed notes
Handwritten notes
Handwritten notes
|
Assignment 13 | Solution 13 | Bonus 13 | Proof of spectral theorem. Rayleigh quotients and their connection to eigenvalues of symmetric matrices. Positive definite matrices, positive semidefinite matrices, Gram matrices. Cholesky decomposition. Singular value decomposition (SVD), derivation of singular value decomposition, connection to eigenvalue decomposition of A^TA and AA^T, compact form of singular value decomposition. Singular values, left singular vectors, right singular vectors. |
| 14 | Dec 22 | CS Lens (Linear Programming) | Mock Exam | Mock Exam Solution | |||
There are 24 different exercise sessions that take place weekly. Two of them are held online, all other sessions take place in-person. Some of the sessions are held in German, others in English, and there is one session in Italian. 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.
| G-01 | German | Focus group | Thu 8-10am | CAB G 56 | |
| G-02 | English | Thu 8-10am | CHN C 14 | ||
| G-03 | English | Thu 8-10am | CHN D 42 | ||
| G-04 | German | Thu 8-10am | CHN D 46 | ||
| G-05 | English | Thu 8-10am | CLA E 4 | ||
| G-06 | Italian | Focus group | Thu 8-10am | HG F 26.5 | |
| G-07 | German | Thu 8-10am | IFW A 32.1 | ||
| G-08 | German | Focus group | Thu 8-10am | ML F 34 | |
| G-09 | German | Focus group | Thu 8-10am | RZ F 21 | |
| G-10 | German | Thu 8-10am | CHN G 42 | ||
| G-11 | German | Thu 8-10am | LFV E 41 | ||
| G-12 | English | Thu 8-10am | HG E 22 | ||
| G-13 | German | Thu 4-6pm | NO C 6 | ||
| G-14 | English | Focus group | Thu 4-6pm | IFW A 34 | |
| G-15 | German | Thu 4-6pm | CHN D 42 | ||
| G-16 | English | Thu 4-6pm | CAB G 52 | ||
| G-17 | English | Focus group | Thu 4-6pm | NO C 44 | |
| G-18 | German | Fri 2-4pm | CHN D 48 | ||
| G-19 | English | Fri 2-4pm | ETZ E 9 | ||
| G-20 | German | Focus group | Fri 2-4pm | IFW A 34 | |
| G-21 | English | Fri 2-4pm | CHN D 42 | ||
| G-22 | English | Fri 2-4pm | CHN G 46 | ||
| G-23 | German | Fri 2-4pm | LFW C 11 | ||
| G-24 | English | Thu 4-6pm | online | ||
