Department of Computer Science | Institute of Theoretical Computer Science

CADMO - Center for Algorithms, Discrete Mathematics and Optimization

Algorithmen und Datenstrukturen

Fall semester 2020, ETH Zürich

Lecturers: Markus Püschel
David Steurer
Organisation: Johannes Lengler
Gleb Novikov
Lectures: Thursday, 14:15 - 17:00 in ML D28
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.

Contents

  • Lectures
  • Exercises
  • Exam information
  • Corona regulations
  • Information about the Moodle forum
  • News:

    The lectures take place on Thursday, 14:15 - 17:00 in ML D28 with the limited number of students in the room. A rotation principle is used so that every student has the opportunity to follow the lecture offline from time to time.

    Lectures

    General information

    The lectures take place on Thursday, 14:15 - 17:00 in ML D28 with the limited number of students in the room. A rotation principle is used so that every student has the opportunity to follow the lecture on-site from time to time. You should check this webpage to see the weeks when your bubble can attend lectures. The other students can follow the lecture online. For online participants, a chat will be available for asking questions (link and password can be found in Moodle).

    Wearing masks is mandatory in ML D28 during the lecture.

    The lecture will be recorded and streamed. The recordings can be found here.

    The first lecture is on Thursday, September 17.

    Lecture notes

    Date Covered topics Notes
    17.09.2020 Introduction.
    • Introduction
    • Grade school multiplication and Karatsuba algorithm
    • Induction
    • O-notation
    Lecture 1
    Optional references (Script): 1.2.1, 1.3.1
    24.09.2020

    Induction and Recursion.

    • Pasture Break
    • Induction
    • Find the Star
    Lecture 2
    Optional References (Skript): 1.2.2,1.4.1
    01.10.2020 Maximum Subarray Sum Problem.
    • Problemdefinition
    • Naiver Algorithmus, Präfixsummen vorberechnen, Divide-and-Conquer-Algorithmus, induktiver Algorithmus
    • Untere Schranken, Problemkomplexität
    Lecture 3
    Optional References (Skript): 1.5
    08.10.2020 Suchen.
    • Lineare Suche
    • Interpolationssuche
    • Binäre Suche
    • Untere Schranke.
    Elementare Sortierverfahren.
    • Bubblesort
    • Sortieren durch Auswahl (Selection Sort)
    • Sortieren durch Einfügen (Insertion Sort)
    • Konzept Invariante
    Lecture 4
    Optional References (Skript): 2.1, 2.2, 2.3

    15.10.2020 Sortieren II
    • Heapsort, Heaps
    • Mergesort
    • Quicksort
    • Untere Schranke Sortieren
    Lecture 5
    Optionale Referenzen (Skript): 2.4 bis 2.7

    Study and reference material

    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 consepts there might differ significantly from the presentation in class.

    There are two scripts relevant for the course, one on algorithms and one on graph theory. 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. You can find a script on graph theory here. 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 Literature

    Exercises

    Exercise sheets

    Exercise sheets Solutions
    Exercise Sheet 0 Solutions for sheet 0
    Exercise Sheet 1 Solutions for sheet 1
    Exercise Sheet 2 Solutions for sheet 2
    Exercise Sheet 3 Solutions for sheet 3
    Exercise Sheet 4 Solutions for sheet 4
    Exercise Sheet 5

    Exercise classes

    The exercises take place on Mondays from 9:15 to 12:00. You can find a seminar room which corresponds to your bubble in the course catalogue.

    Wearing masks is mandatory in seminar rooms during exercise classes.

    Every Monday (starting from September 21) 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 21. It is important to attend it, since your teaching assistant (TA) will partition you into working groups of 2 (or 3) people, and then you 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 21, and the solutions should be submitted in the beginning of the exercise class on September 28). 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).

    All exercise sheets are written in English. You can hand in your solutions either in English or in German. Chris Wendler 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.

    Online exercise class

    One exercise class (out of 24) will take place online (link and password can be found in Moodle). Students in isolation or quarantine, or who feel any corona-related symptoms should attend the online class. In this case, a student of group X who switch to the online group

  • must inform the TA of X before the class that they go the online group;
  • still needs to hand in their theory assignment to the TA of X at the beginning of the exercise class, either via their working group partner, or via email;
  • still needs to peer grade together with their working group partner during the last hour of the exercise class (via skype/zoom + pdf annotation);
  • still needs to work together (online) during the week with their working group partner to solve the next exercise sheet.
  • Students who need to participate in the online class permanently should contact us at the beginning of semester. In particular, this option is available for students who are in a risk group for Covid-19, or who live in the same household with such a person.

    Programming exercises

    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 ('Welcome' and 'Median of Three'). These warm-up exercises do not give any bonus points.

    The first programming assignment with bonus points will be published in the Code Expert website on October 12.

    You can find the online documentation on Code Expert here. The following things are different to what is stated in the documentation:

    Important:

    Programming exercises are created by Chih-Hung Liu. 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.

    Bonus points

    During the semester, the students can get bonus points for

  • solving the designated parts of the theoretical exercise sheets (in working groups);
  • peer grading the specified part of the theory sheets during the class (in working groups);
  • solving the programming problems (individually).
  • 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.

    Participation in the bonus system is voluntary. It is possible to get a 6.0 without participating in the bonus system.

    Each working group must hand in their own, independent solution. 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.

    Exam information

    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.

    Further details will be provided later, additional information relevant for the exam can be found in the course catalogue.

    Regulations during the coronavirus pandemic

    Students will be assigned to so called "bubbles", i.e. exercise groups that persist throughout the semester and between different courses. There is no social distancing required within a bubble. Wearing masks is mandatory in seminar rooms during exercise classes.

    The lectures take place on Thursday, 14:15 - 17:00 in ML D28 with the limited number of students in the room. A rotation principle is used so that every student has the opportunity to follow the lecture on-site from time to time. You should check this webpage to see the weeks when your bubble can attend lectures. The other students can follow the lecture online. For online participants, a chat will be available for asking questions (link and password can be found in Moodle).

    Wearing masks is mandatory in ML D28 during the lecture.

    One exercise class (out of 24) will take place online. Students in isolation or quarantine, or who feel any corona-related symptoms should attend the online class (link and password can be found in Moodle). They need to inform their teaching assistant (TA) about that, and they still need to hand in their exercises to their regular TA and participate in the peer grading in their regular exercise group (both remotely). Students who need to participate in the online class permanently should contact us at the beginning of semester. In particular, this option is available for students who are in a risk group for Covid-19, or who live in the same household with such a person.

    Further information will be provided later.

    Forum

    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-AAL. Further information can be found in the course catalogue.