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
| Lecturers: |
Patrick Schnider (OAT Z 13.1) |
|---|---|
| Assistants: |
Simon Weber (OAT Z 18), contact assistant Anton Künzi |
| Lectures: |
Thu 13-14, CAB G 51, Fri 12-14, CAB G 61 |
| Exercise: | Wed 10-12, CHN F 46 |
| Language: | English |
| Contents: |
Fundamental concepts, techniques and results in Topological Data Analysis.
Preliminary list of topics:
|
| Literature: |
The lecture notes can now be found here: Lecture Notes These are a collection of the scribe notes from each lecture, see below. We will also list the relevant chapters in the textbooks below (using their abbreviations). The main textbook for the course is:
|
| Prerequisites: | The course assumes knowledge of discrete mathematics, algorithms and data structures and linear algebra, as supplied in the first semesters of Bachelor Studies at ETH. |
| Special Assignment 1: | 23.03. - 06.04. (Deadline is at 13:15) | Exercise Sheet 1 |
|---|---|---|
| Special Assignment 2: | 04.05. - 19.05. (Deadline is at 12:15). | Exercise Sheet 2 |
Absence. If there are compelling reasons why you cannot hand in a special assignment on the due date foreseen, please contact us post-haste and we can look for a solution. Note, however, that we will grant requests of this type only in very exceptional cases (doctor's note, military service, funeral, etc.). Private events (vacation, sports, career fairs, etc.) are never sufficient grounds. As far as special assignments are concerned, you can hand them in to the contact assistant by email at any time before the due date, so there is no need to be present in person. Regarding the final exam, ETH regulations apply.
Exchange students. Exchange students enrolled for TDA in spring might want to return to their home university prior to the date of the final exam. If this applies to you and you nonetheless wish to be evaluated and given credits for TDA, then please take a look at the following website for current regulations.
In the table below you can find the lecture dates and the preliminary topics. The exercises and their solutions will be published here.
| Date | Content | Exercises and links | Scribe notes | Relevant book chapters |
| #1 23.02.2023 | Information about the course, Intro to Topological Spaces | Slides | Scribe 1 | [CTDA] 1.1 |
| #2 24.02.2023 | Mathematical Background | Exercises 1 | Scribe 2 | [CTDA] 1.1, 1.2, 1.3 |
| #3 02.03.2023 | Some Algebra | Scribe 3 | [CTDA] 2.4 | |
| #4 03.03.2023 | Simplicial Complexes | Slides, Exercises 2 | Scribe 4 | [CTDA] 2.1, 2.2 |
| #5 09.03.2023 | Chains and Boundaries | Scribe 5 | [CTDA] 2.4, 2.5 | |
| #6 10.03.2023 | Homology | Exercises 3 | Scribe 6 | [CTDA] 2.5 |
| #7 16.03.2023 | Homology of spheres | Scribe 7 (updated on 17.03.!) |
||
| #8 17.03.2023 | Induced Homology, Brouwer fixed-point theorem, Intro to Persistence |
Exercises 4 | Scribe 8 (updated on 22.03.!) |
[CTDA] 2.5.1 |
| #9 23.03.2023 | Persistent Homology | Slides | Scribe 9 | [CTDA] 3.1, 3.2 |
| #10 24.03.2023 | Persistent Homology, Algorithms | Slides Exercises 5 |
Scribe 10 | [CTDA] 3.1, 3.2 |
| #11 30.03.2023 | Complexes on Point Clouds (online) | Slides | [CTDA] 2.2, 2.3 | |
| #12 31.03.2023 | Tutorial on Programming in TDA | Colab Exercises 6 | ||
| #13 06.04.2023 | Guest Lecture by Bastian Rieck on TDA in Machine Learning | Slides | Recording | |
| #14 20.04.2023 | Complexes on Point Clouds (cont'd) | Exercises 7 | Scribe 11&14 | [CTDA] 2.2, 2.3 |
| #15 21.04.2023 | Distance Measures and Stability | Exercises 8 | Scribe 15 | [CTDA] 3.2.1, [Comp.] VIII.2 |
| #16 27.04.2023 | Wasserstein Distance | Scribe 16 | [CTDA] 3.2.1 | |
| #17 28.04.2023 | Interleaving Distance | Exercises 9 | Scribe 17 | [CTDA] 3.4 |
| #18 04.05.2023 | Interval Modules, Structure Theorem | Exercises 10 | Scribe 18 | [CTDA] 3.4 |
| #19 05.05.2023 | Reeb Graphs | Slides | Scribe 19 | [CTDA] 7 |
| #20 11.05.2023 | Distance Measures for Reeb Graphs | Exercises 11 | Scribe 20 | |
| #21 12.05.2023 | Functional distortion distance, Mapper | Colab (Mapper demo) | Scribe 21 | |
| #22 19.05.2023 | Guest Lecture: Marius Huber (UZH) | Slides, Jupyter Notebook | ||
| #23 25.05.2023 | Multi-scale Mapper | TDA Challenge | Scribe 23 | [CTDA] 9.3 |
| #24 26.05.2023 | Optimal Generators | Exercises 12 Slides | Scribe 24 | [CTDA] 9.2 |
| #25 01.06.2023 | Applications | Slides | Scribe 25 | |
| #26 02.06.2023 | Applications | Scribe 26 | ||
Every week we provide you with exercises. The students are split into small groups, and the members of each group work together. At the end of the session, for each exercise, a student from a group presents their solution to the rest of the students. In addition to the exercise sessions, we encourage you to solve the exercises in written form and to hand in your solutions to the teaching assistant. Your solutions are thoroughly commented, but they do not count towards your final grade. The motivation to work on the exercises stems from your interest in the topic (and possibly also the desire to succeed in the exam).
In addition, you receive two special assignments during the semester. The special assignment is to be solved in written form and you have two weeks of time to return your solutions/reports, typeset in LaTeX. In contrast to the exercises, these special assignments do count towards the final grade: Your two grades will account for 20% of your final grade each. Solving the special assignments in teams is not allowed. Besides one or two exercises, the special assignments may include a small research project, or you are asked to give a short talk about your last small research project. The format of this talk will be determined by the number of students who register for the course.
There is an oral exam of 30 minutes during the examination period. Your final grade consists to 60% of the grade for the exam and to 40% of the grade for the homework assignments.
You are expected to learn proofs discussed in the lecture, should be able to explain their basic ideas and reproduce more details on demand. You should also be able to give a short presentation on any topic treated throughout the course. One of the questions given to you during the exam is to solve one of the exercises posed throughout the semester. Roughly half an hour before the exam you get to know the exercise to be solved and one topic that you will be questioned about in particular, that is, you have 30 minutes preparation time. For this preparation, paper and pens will be provided. You may not use any other material, like books or notes.
For PhD students, the same rules apply for obtaining credit points as for all other participants. Taking the exam and achieving an overall grade of at least 4.0 (computed as a weighted average of grades for homework and the oral final exam as detailed above) qualifies for receiving credits. In order to comply with new regulations recently issued by the department, merely attending the course and/or handing in exercises is no longer sufficient.
This course is complemented by a special type of seminar Projects in Topological Data Analysis in the following fall semester. In this seminar, students from four different universities will collaborate on projects in Topological Data Analysis in an international setting. After having completed the course, it is possible to do a semester, master or diploma thesis in the area.
