Department of Computer Science | Institute of Theoretical Computer Science
Department of Computer Science | Institute of Theoretical Computer Science
Fall semester 2021, ETH Zürich
| Lecturers: | Markus Püschel David Steurer |
| Organisation: | Gleb Novikov Tommaso d'Orsi |
| Lectures: | Thursday, 10:15 - 12:00; 14:15 - 15:00 |
| Exercises: | Monday, 9:15 - 12:00 |
If you have any questions about organisation of the course (NOT related to the content of lectures or exercises), you can send us an email to the following address: organisation.ad@lists.inf.ethz.ch. Additional information about the course can be found in the course catalogue.
Information for students of the "Computational Biology and Bioinformatics Master" programme.
There is a general requirement to wear masks in all courses, labs and student workspaces. Distancing requirements should be observed wherever possible. COVID certificates are compulsory for all face-to-face teaching events.
Your certificate may be checked before the start of each lecture. To speed up the process, please keep your ID and certificate at hand.
Your certificate will be checked before the start of each exercise class. To speed up the process, please keep your ID and certificate at hand.
Further guidelines may appear according to ETH regulations.
The lectures take place on Thursday, 10:15 - 12:00; 14:15 - 15:00.
The lecture will be held physically in the lecture rooms according to ETH regulations. In particular wearing masks is mandatory, and it is compulsory to have a valid COVID certificate.
Until new guidelines will be received, we kindly ask you to keep your certificate and your ID at hand when you attend the lecture physically. Once you will be seated in the classroom, we will randomly check some of your certificates. This process will take place before the starting of the lecture. We will also randomly check the certificates before the second part of the lecture (i.e the part that starts at 14:15).
All lectures will be streamed live: here the first part of the lecture (10:15 - 12:00), and here the second part of the lecture (14:15 - 15:00). Also the lectures will be recorded for later viewing.
| Date | Covered topics | Notes |
|---|---|---|
| 23.09.2021 | Introduction
|
Lecture 1 |
| 30.09.2021 | Asymptotic notation
|
Lecture 2 |
| 07.10.2021 |
Maximum Subarray Sum Problem
|
Lecture 3 |
| 14.10.2021 |
Searching algorithms
|
Lecture 4 |
| 21.10.2021 |
Sorting algorithms II
|
Lecture 5 |
| 28.10.2021 |
Dynamic Programming
|
Lecture 6 |
| 04.11.2021 |
Dynamic Programming II
|
Lecture 7 |
| 11.11.2021 |
Graphs
|
Lecture 8 Additional reference: Graphs and Eulerian tours |
| 18.11.2021 |
Data Structures and Abstract Data Types
|
Lecture 9 (updated) |
| 23.11.2021 |
Graph algorithms
|
Lecture 10 |
| 25.11.2021 |
Graph algorithms II
|
Lecture 11 |
| 02.12.2021 |
Shortest Paths
|
Lecture 12 |
| 09.12.2021 |
Minimum Spanning Tree
|
Lecture 13 |
| 16.12.2021 |
Shortest paths 2
|
Lecture 14 |
| 23.12.2021 |
Mediane
|
Lecture 15 |
Primary study material are the handwritten notes for the individual lectures. You can use the scripts and books as optional reference material, however the presentation of some concepts there might differ significantly from the presentation in class.
There are several scripts which cover parts of the course. They are additional material, and not per se exam-relevant. You can download the script for algorithms as a PDF-file within the ETH network. Note that the script does not exactly match the course material. In particular, it is more extensive than the course material. For the graph theory part, you can find a script as html or pdf. There is also an older (more extensive, but less adapted to the lecture) script on graph theory here. More additional materials (e.g. old exercises) can also be found on the web page of the previous year.
For further reading, the book ``Algorithmen und Datenstruktur'', T. Ottmann and P. Widmayer, 6th edition, Spektrum Verlag, 2017, is recommended. You can find it in the ETH Store or download it as a PDF-file within the ETH network. Note, however, that the notions of the book do not always match those of the lecture, e.g. the book uses a different definition of the O notation.
Additional LiteratureThe exercise classes take place on Mondays from 9:15 to 12:00.
Wearing masks is mandatory in seminar rooms during exercise classes, as per ETH regulations.
Your certificate will be checked before the start of each exercise class. To speed the process, please keep your ID and certificate at hand.
Every Monday (starting from 27/09/2021) we will publish a new theory exercise sheet on the webpage, and you have one week to solve the exercises from this sheet.
The first exercise class takes place on Monday, September 27. It is important to attend since your teaching assistant (TA) will partition you into working groups of 2 (or 3) people. Then you will solve exercises from the current sheet together within the working group. The solutions (one solution per working group) should be handed in at the beginning of the exercise class next Monday (for example, the first exercise sheet is published on September 27, and the solutions should be submitted in the beginning of the exercise class on October 04). The working groups are reassigned every 3 weeks (by the TA).
During the last hour of the exercise class you will peer-grade the solutions of your fellow students: the TA distributes the solutions among working groups (each working group gets the solution of some other working group), and then asks students to read the solutions and write their comments if they think that they are incorrect or incomplete (comments should contain a clear explanation). After peer grading, you should send your comments to your TA by email.
All exercise sheets are written in English. You can hand in your solutions either in English or in German. Rajai Nasser and Ulysse Schaller are responsible for the content of theoretical exercises. If you have any content-related questions about theory exercises, please send an email to the following address: exercises.ad@lists.inf.ethz.ch.
Since this semester ETH requires COVID certificates for attending in person lectures and exercise classes, the only way to participate in exercise sessions for students who are not able to get the certificate is to attend one of the online exercise classes.
Students who want to participate in the online class for the whole semester should contact us at the beginning of semester. As a subject of your email, please use the key word ONLINECLASS.
We encourage you to participate in on-site class if it is possible for you, but if you plan to participate in online class for more than 3 weeks, then you should not participate in on-site class, so in this case you can only participate in online class for the whole semester. If you have a strong reason to participate online for more than 3 weeks, but then you really want to participate on-site, please write us an email to organisation.ad@lists.inf.ethz.ch describing your situation.
If you are registered for an on-site class but one day you cannot attend, there is a catch-all online class (in English) that you can join at this Zoom link (notice that a ethz account is required). You are supposed to return to your original on-site class at the first date possible. If you participate in the bonus points system you will need to submit your solution to the teaching assistant responsible for your class (not the catch-all online one!). Similarly, you will need to do the peer grading within your original group. More details will be provided in the first exercise class.
A gentle introduction on how to implement algorithms in practice can be found in this pdf (here the interactive version can be accessed via your ethz account). The aim of this document is to show how to translate the high level algorithmic ideas discussed in class into actual Java code. This material is optional and not considered to be part of the course (notice that the programming exercises on Code Expert are part of the course). If needed, you can find an introduction to programming in Java at this link (this material is also optional and not considered part of the course).
The online judging system for programming exercises is Code Expert (https://expert.ethz.ch/). You have two warm-up exercises in the Code Expert website to test the environment. These warm-up exercises do not give any bonus point. This pdf explains how to complete one warm-up exercise. More detailed information about the Code Expert system, can be found in the on-line documentation.
For each set of programming exercises you will have two weeks to submit your solution. For example, the first Programming Exercise Sheet will be published on Thursday 14/10/2021 and the deadline for submission will be 23:59 Thursday 28/10/2021.
Programming exercises are created by Chih-Hung Liu and Rares Darius Buhai. They are NOT related to the exercise classes and your TAs are not supposed to answer any questions about programming exercises. Questions regarding programming exercises can and should be submitted through the messaging system of Code Expert. This will be the only way of asking questions during the computer part of the exam. We also remark that there is a Moodle Forum in which you can discuss the programming exercises.
Important:
During the semester, the students can get bonus points for
At the end of the term, the bonus points are translated into a bonus grade between 0 and 0.25. The final grade is then the sum of the exam grade and the bonus grade (rounded and capped at 6.0). The students already get the maximal bonus grade (0.25) for 80% of the bonus points. This compensates for possible absences, e.g. due to illness or military service. That is, the formula for the bonus grade is min(0.25, 0.25 * n_points / (0.8 * max_points)), where n_points is your number of bonus points, and max_points is the maximal possible number of bonus points.
Participation in the bonus system is voluntary. It is possible to get a 6.0 without participating in the bonus system.
Peer graded solutions must be submitted by the peer graders no later than 23:59 on the same day of the exercise class.
Each working group must hand in their own, independent solution of the theory exercises. Likewise, programming exercises must be handed in with self-written code. We recommend solving all tasks without the help of external sources (books, internet, solutions from fellow students), as otherwise the learning effect of the tasks is largely lost. Even if you seek advice from an outside source, plagiarism (partial or complete) is not allowed. In this case, we recommend that you put this source aside after reading it and then formulate your solution (on your own!) the next day. Correspondingly, copying third-party code (in whole or in part, also from the Internet) to solve programming tasks is not permitted. The regulation on external sources also applies here by analogy. You are of course allowed to use Java documentation when programming, and in particular to search for syntax. You are not allowed to make your own solutions (whether theory or programming) available for copying. In case of copying, both involved working groups/students lose their points, regardless of whose solution was the original. Moreover, it can lead to further consequences for both working groups/students.
The exam takes place in the exam session. It consists of two parts, a written theory part and a programming part.
The exercises (theoretical and programming) that we suggest you to solve during the semester are designed to optimally prepare for the exam.
You can find a list of some exams from previous years here.
Technical details on the written exam like allowed aids can be found here. More information will be sent by email in the weeks before the exam.Further details will be provided later, additional information relevant for the exam can be found in the course catalogue.
The Moodle-Forum is supposed to be used for discussions among the students, but we will check the forum at least twice a week to ensure that it does not contain wrong information. Please follow the following no-spoiler policy: If your answer directly or indirectly contains tips or solution hints for an exercise, then put a clear spoiler warning at the beginning of your post and write the critical part of the post (the possible Spoiler) in white text color. In this way, you enable your fellow students to solve the tasks independently, without accidentally reading your post or the possible hints. Please provide your fellow students with a spoiler-free learning environment by following a corresponding policy in private communication channels (Telegram groups etc.)!
Formulated solutions (partial or complete) must not be published in the forum or in a Telegram group! This applies to both theory and programming tasks.
Important note for students of the "Computational Biology and Bioinformatics Master" programme: If your study administration has made the course "Data Structures and Algorithms" mandatory, you will not be able to participate in this course. Instead, you must take the course Nr. 252-0002-AAR. Further information can be found in the course catalogue.