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 6page summary to the exam, the official guidelines for this (copied from VVZ) are: "6 A4Seiten 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 (DeutschEnglisch 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 autocorrected 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 handin exercises are NOT graded and do not count towards your bonus.
The autocorrected 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 webinterface 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 Clickerquestions 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 autocorrected 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 "CSLens" (typically, these are slides). This material highlights connections of the course content with Computer Science. Material marked as "CSLens" 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, CauchySchwarz inequality, triangle inequality, perpendicular vectors, hyperplanes; compute with matrices: matrixvector 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 CSLens (associativity) 
Assignment 2  Solution 2  Bonus 2  perform matrix multiplication, including matrix vector, vectormatrix, 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 CSLens (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 CSLens (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 innerproduct. Projections with orthonormal bases. Build an orthonormal basis with GramSchmidt (and show correctness of GramSchmidt). 
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. Pseudoinverse, definition and properties. Pseudoinverse and least squares for full column rank matrices. Pseudoinverse 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, cofactors 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. Complexvalued 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 inperson. 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.
G01  German  Focus group  Thu 810am  CAB G 56  
G02  English  Thu 810am  CHN C 14  
G03  English  Thu 810am  CHN D 42  
G04  German  Thu 810am  CHN D 46  
G05  English  Thu 810am  CLA E 4  
G06  Italian  Focus group  Thu 810am  HG F 26.5  
G07  German  Thu 810am  IFW A 32.1  
G08  German  Focus group  Thu 810am  ML F 34  
G09  German  Focus group  Thu 810am  RZ F 21  
G10  German  Thu 810am  CHN G 42  
G11  German  Thu 810am  LFV E 41  
G12  English  Thu 810am  HG E 22  
G13  German  Thu 46pm  NO C 6  
G14  English  Focus group  Thu 46pm  IFW A 34  
G15  German  Thu 46pm  CHN D 42  
G16  English  Thu 46pm  CAB G 52  
G17  English  Focus group  Thu 46pm  NO C 44  
G18  German  Fri 24pm  CHN D 48  
G19  English  Fri 24pm  ETZ E 9  
G20  German  Focus group  Fri 24pm  IFW A 34  
G21  English  Fri 24pm  CHN D 42  
G22  English  Fri 24pm  CHN G 46  
G23  German  Fri 24pm  LFW C 11  
G24  English  Thu 46pm  online  