Algorithmen und Datenstrukturen

This is a web page related to Fall semester 2019. It is NOT relevant for Fall semester 2020.

Herbstsemester 2019, ETH Zürich

Weitere Informationen zur Vorlesung und verbindliche Informationen zur Prüfung finden Sie im Vorlesungsverzeichnis.

Wichtiger Hinweis für Studierende des Studiengangs "Computational Biology and Bioinformatics Master": Falls Ihr Studiensekretariat Ihnen den Kurs "Data Structures and Algorithms" zur Auflage gemacht hat, können Sie an diesem Kurs nicht teilnehmen. Stattdessen müssen Sie den Kurs zum Selbststudium, Nr. 252-0002-AAL, belegen. Weitere Informationen finden Sie im Vorlesungsverzeichnis.

News:

• 30.02.: Die Prüfung vom Winter ist mit Lösung online.
• 08.01.: Update technical guide.
• 08.01.: Zusätzliche Klausurinformationen und Links (am Ende der Webseite).
• 02.01.: Solutions for P11 and P13 are online.
• 20.12.: Solution for Sheet 13 is online.
• 19.12.: Sheet 13 is online. There are no bonus points, but the material is relevant for the exam.
• 19.12.: Vorlesungsnotizen für Vorlesung 15 online.
• 13.01.: Typo aus Vorlesungsnotizen für Graphalgorithmen II entfernt.

Vorlesung

Die Inhaltsangaben zur Vorlesung, Angaben zu Literatur und Links werden auf dieser Seite laufend aktualisiert.

Hier finden Sie ausserdem eine Liste einiger Prüfungen der vergangenen Jahre.

Datum	behandelte Themen	Unterlagen
19.09.2019	Einführung. Einführung, Organisation Elementare Operationen Schulmultiplikation und Algorithmus von Karatsuba, Teil 1	Vorlesungsnotizen Optionale Referenzen (Skript): 1.2.1
26.09.2019	Graphentheorie. Algorithmus von Karatsuba, Teil 2 O-Notation Induktion Finde den Star	Vorlesungsnotizen Optionale Referenzen (Skript): 1.2,1.3,1.4.1
03.10.2019	Maximum Subarray Sum Problem. Problemdefinition Naiver Algorithmus, Präfixsummen vorberechnen, Divide-and-Conquer-Algorithmus, induktiver Algorithmus Untere Schranken, Problemkomplexität	Vorlesungsnotizen Optionale Referenzen (Skript): 1.5
10.10.2018	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	Vorlesungsnotizen Optionale Referenzen (Skript): 2.1 bis 2.3
17.10.2019	Sortieren II Heapsort, Heaps Mergesort Quicksort Untere Schranke Sortieren	Vorlesungsnotizen Optionale Referenzen (Skript): 2.4 bis 2.7
24.10.2019	Dynamische Programmierung I Längste aufsteigende Teilfolge Längste gemeinsame Teilfolge Editierdistanz	Vorlesungsnotizen Optionale Referenzen (Skript): 3.1 bis 3.5
31.10.2019	Dynamische Programmierung II Teilsummenproblem (Subset Sum) Rucksackproblem (Knapsack) Approximation Matrixmultiplikation	Vorlesungsnotizen Optionale Referenzen (Skript): 3.5 bis 3.7
07.11.2019	Abstrakte Datentypen/Datenstrukturen Stapel Schlange Prioritätswarteschlange Suchbäume Natürliche Suchbäume AVL-Bäume	Vorlesungsnotizen Optionale Referenzen (Skript): 4.1, 4.4, 4.5
14.11.2019	Graphen Einführung Graphen Eulertouren Datenstrukturen von Graphen I	Vorlesungsnotizen Optionale Referenzen (Skript): 5.1.1, 5.1.2
19.11.2019	Graphenalgorithmen gerichtete Graphen Topologische Sortierung Tiefensuche (Depth First Search)	Vorlesungsnotizen Optionale Referenzen (Skript): 5.2.1., 5.4
21.11.2018	Graphenalgorithmen II Tiefensuche (Fortsetzung) Pre-/post-Ordnung Forward/backwards/cross edges, Finden von Zykeln Breitensuche	Vorlesungsnotizen Optionale Referenzen (Skript): 5.2
28.11.2019	Kürzeste Wege Kürzeste Wege Algorithmus von Bellman-Ford Algorithmus von Dijkstra	Vorlesungsnotizen Optionale Referenzen (Skript): 5.5.2, 5.5.3
05.12.2019	Minimale Spannbäume Minimale Spannbäume Algorithmus von Boruvka Algorithmus von Prim, Verbindung zu Dijkstra's Algorithmus Algorithmus von Kruskal Datenstruktur: Priority Queues Datenstruktur: Union-Find	Vorlesungsnotizen Optionale Referenzen Buch: Kapitel 9.3, Skript: 4.1
12.12.2019	Kürzeste Wege 2 Algorithmus von Floyd-Warshall Algorithmus von Johnson Berechnung der Anzahl Wege durch Matrixmultiplikation Matrixmultiplikation nach Strassen	Vorlesungsnotizen Optionale Referenzen Skript: 5.5.4
19.12.2019	Mediane Auswahlproblem, Mediane	Vorlesungsnotizen

Literatur zur Vorlesung

Es gibt zwei Skripte, eins zu Algorithmen und eines zur Graphentheorie, die mit der Vorlesung abgestimmt sind. Das Skript zu Algorithmen können Sie bereits innerhalb des ETH-Netzes als PDF-Datei herunterladen. Beachten Sie, dass das Skript nicht deckungsgleich zur Vorlesung ist. Insbesondere ist es umfangreicher als die Vorlesung. Ausserdem gibt es vom Vorjahr ein Skript zur Graphentheorie. Zusätzliche Materialien (z.B. alte Übungen) finden Sie auch auf der Webseite des Vorjahres.

Zur weitergehenden Lektüre ist das Buch ''Algorithmen und Datenstrukturen'', T. Ottmann und P. Widmayer, 6. Auflage, Spektrum Verlag, 2017, empfehlenswert. Dieses können Sie bei der Polybuchhandlung beziehen oder innerhalb des ETH-Netzes als PDF-Datei herunterladen. Beachten Sie aber, dass die Konventionen des Buches nicht immer mit denen der Vorlesung übereinstimmen, z.B. verwendet das Buch eine andere Definition der O-Notation.

Weitere Literatur

• Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. 1994. Concrete Mathematics: A Foundation for Computer Science (2nd ed.). Addison-Wesley Longman Publishing Co.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd ed.). MIT Press.

Übungen

Die Übungen finden jeweils am Montag von 9:15 bis 12:00 Uhr statt. .

Erster Übungstermin ist Montag, der 23. September. Das erste Übungsblatt wird ebenfalls am Montag, dem 23. September veröffentlicht. Alle Übungsblätter sind auf Englisch verfasst. Inhaltlich verwantwortlich für die theoretische Übungen sind Gleb Novikov und Chris Wendler. Bei inhaltlichen Fragen posten Sie bitte (auf Englisch) ins Moodle-Forum. Bei organisatorischen Fragen wenden Sie sich an Johannes Lengler.

Übungsblätter	Lösungen
Übungsblatt 0	Beispiellösung Blatt 0
Übungsblatt 1	Beispiellösung Blatt 1
Übungsblatt 2	Beispiellösung Blatt 2
Übungsblatt 3	Beispiellösung Blatt 3
Übungsblatt 4 Programmieraufgaben P5 Vorlage P5.1 Vorlage P5.2 Vorlage P5.3 (challenge problem) Technische Anleitung Vorlage P5.0	Beispiellösung Blatt 4 Beispiellösung P5.1 Beispiellösung P5.2 Beispiellösung P5.3
Übungsblatt 5	Beispiellösung Blatt 5
Programmieraufgaben P7 Vorlage P7.1 Vorlage P7.2	Beispiellösung P7.1 Beispiellösung P7.2
Übungsblatt 6	Beispiellösung Blatt 6
Übungsblatt 7	Beispiellösung Blatt 7
Übungsblatt 8	Beispiellösung Blatt 8
Programmieraufgaben P9 Vorlage P9.1 Vorlage P9.2 Vorlage P9.3 (no bonus points, just for practise)	Beispiellösung P9.1 Beispiellösung P9.2
Übungsblatt 9	Beispiellösung Blatt 9
Übungsblatt 10	Beispiellösung Blatt 10
Programmieraufgaben P11 Vorlage P11.1 Vorlage P11.2 Vorlage P11.3 (no bonus points)	Beispiellösung P11.1 Beispiellösung P11.2 Beispiellösung P11.3
Übungsblatt 11	Beispiellösung Blatt 11
Programmieraufgaben P13 Vorlage P13.1 Vorlage P13.2	Beispiellösung P13.1 Beispiellösung P13.2
Übungsblatt 12	Beispiellösung Blatt 12
Übungsblatt 13	Beispiellösung Blatt 13

Organisation und Ablauf der Übungen

Jede Woche wird montags nach der Übung auf dieser Seite ein Übungsblatt mit theoretischen Aufgaben veröffentlicht. In späteren Wochen werden zusätzlich Programmieraufgaben veröffentlicht.

Sie lösen die wöchentlichen Theorie-Übungsblätter in Arbeitsgruppen von zwei Personen. Einzelabgaben werden nicht akzeptiert. Sie geben die gemeinsame Lösung (für die Gruppe) in der darauffolgenden Woche zu dem Beginn Ihrer Übungsgruppe ab. Die Lösung ist eine Gemeinschaftsaufgabe. Sie müssen vor Abgabe sicherstellen, dass beide Mitglieder der Gruppe die Lösung verstanden haben und auf Aufforderung erklären können.

Die Arbeitsgruppen werden in der Übungsstunde festgelegt. Die Gruppen werden im Laufe des Semesters alle 4 Wochen neu eingeteilt. Da die erste Einteilung in der Übungsstunde am 23.09. stattfindet, ist es wichtig, dass Sie an dieser Stunde teilnehmen. Sollten Sie aus irgendeinem Grund an diesem Tag verhindert sein, dann teilen Sie dies unbedingt Ihrer Übungsgruppenassistentin mit, entweder direkt per E-Mail, oder über Ihre Kommilitonen. Wir werden keine Einzel-Abgaben akzeptieren.

In den Übungen werden die Aufgaben besprochen. Anschliessend wird ein Teil der eingereichten Lösung einer Gruppe von einer anderen Gruppe bewertet und mit Kommentaren (Peer Feedback) versehen am Ende der Übungsstunde bei der Übungsassistentin abgegeben. Die Assistentin wird sowohl das Blatt als auch die Korrektur bis zur darauffolgenden Übungsstunde bewerten.

Programmieraufgaben

Ab dem zweiten Monat im Semester gibt es zusätzlich auch Programmieraufgaben. Diese werden alleine (nicht in Gruppen) gelöst. Die Programmieraufgaben schicken Sie online an einen Judge, der die Lösung automatisch testet und bewertet. Eine Anleitung dazu werden wir auf dem ersten Programmierblatt bereitstellen.

Die Programmieraufgaben werden von Karel Kubicek betreut. Bei Fragen zum Judge oder zu den Programmieraufgaben posten Sie bitte (auf Englisch) ins Moodle-Forum.

Bonuspunkte

Sie können im Laufe des Semesters Bonuspunkte für die Teilnahme am Übungsbetrieb erwerben, die später in Ihre Endnote eingehen. Sie erhalten Bonuspunkte für

• Das Lösen der theoretischen Übungsblätter.
• Die Qualität Ihres Peer Feedbacks.
• Das Lösen der Programmieraufgaben.

Für jedes Theorie-Blatt, jedes Peer Feedback, und jedes Programmierblatt können Sie Bonuspunkte erreichen.

Am Ende des Semesters wird aus den Bonuspunkten eine Bonusnote für die Übungen berechnet. Diese Bonusnote liegt zwischen 0 und 0.25 und wird zu Ihrer Note in der Sessionsprüfung addiert. Der Maximalbonus ist schon mit 80% der Punkte erreicht. Dies kompensiert allfällige Absenzen, z.B. durch Krankheit oder Militärdienst.

Die Teilnahme am Bonussystem ist freiwillig. Es ist möglich, eine 6.0 in der Vorlesung zu erhalten, ohne am Bonussystem teilzunehmen.

All Ihre Abgaben müssen eigenständig formuliert und verfasst sein. Wir empfehlen, alle Aufgaben ohne Zuhilfenahme externer Quellen (Bücher, Internet, Lösungen von Mitstudentinnen) zu lösen, da der Lerneffekt der Aufgaben sonst weitgehend verloren geht. Selbst wenn Sie eine externe Quelle zu Rate ziehen, ist Plagiarismus (egal ob teilweise oder vollständig) nicht erlaubt. In diesem Fall empfehlen wir Ihnen, diese Quelle nach dem Lesen wegzulegen, und dann erst am nächsten Tag Ihre Lösung (eigenständig!) zu formulieren. Entsprechend ist das Kopieren von fremden Code (ganz oder teilweise, auch aus dem Internet) zur Lösung der Programmieraufgaben nicht erlaubt. Die Regelung zu fremden Quellen gilt sinngemäss auch hier. Sie dürfen aber natürlich beim Programmieren eine Java-Dokumentation verwenden, und insbesondere Syntax nachschlagen. Sie dürfen Ihre eigenen Lösungen (egal ob Theorie oder Code) nicht zum Abschreiben zur Verfügung stellen. Plagiarismus führt zur Aberkennung der Bonuspunkte für beide Versionen, Original und Plagiat, und zieht weitere Konsequenzen nach sich.

Sie können Ihre Bonuspunkte unter echo einsehen. Die Bonuspunkte erscheinen dort mit ca. zweiwöchiger Verzögerung. Bitte prüfen Sie regelmässig, ob die neuen Bonuspunkte korrekt sind. Wenn Sie bei einem Eintrag zu einem Theorieblatt (Lösung oder Peer Grading) der Meinung sind, dass er inkorrekt ist, dann kontaktieren Sie bitte zeitnah Ihre Übungsgruppenleiterin. Wenn Sie bei einem Programmiereintrag der Meinung sind, dass er inkorrekt ist, dann kontakieren Sie bitte Karel Kubíček.

Forum

Im Moodle-Forum können Sie einerseits Fragen an uns stellen, Sie können das Forum jedoch auch dazu nutzen, um untereinander über die Übungen zu diskutieren. In diesem Fall befolgen Sie bitte die folgende No-Spoiler-Policy: Wenn Ihre Antwort direkt oder indirekt Tipps oder Lösungshinweise zu einer Übungsaufgabe enthält, dann stellen Sie an den Anfang Ihres Posts eine klare Spoilerwarnung und verfassen Sie den kritischen Teil des Posts (den möglichen Spoiler) in weisser Textfarbe. Auf die Weise ermöglichen Sie Ihren Kommilitonen, die Aufgaben eigenständig zu lösen, ohne Ihren Post und die möglichen Hinweise aus Versehen zu lesen. Bitte ermöglichen Sie Ihren Kommilitonen eine Spoiler-freie Lernumgebung, indem Sie eine entsprechende Policy auch in privaten Kommunikationskanälen (Telegram-Gruppen etc) befolgen!

Ausformulierte Lösungen (egal ob teilweise oder vollständig) gehören weder ins Forum noch in eine Telegram-Gruppe! Das gilt sowohl für Theorie-Aufgaben als auch für Programmieraufgaben.

Prüfung und Note

Die Prüfung findet in der Prüfungssession statt. Sie besteht aus zwei Teilen, einem schriftlichen Theorieteil (2 Stunden) und einem Programmierteil über den Judge (3 Stunden). Die Prüfungsnote ergibt sich aus dem gewichteten Mittel aus dem Theorieteil (60%) und dem Programmierteil (40%). Zur Bestimmung der Endnote wird anschliessend die Bonusnote addiert, und bei 6.0 abgeschnitten. Die Übungsaufgaben während des Semesters sind so ausgelegt, dass sie optimal auf die Prüfung vorbereiten.

Technischer Ablauf

Alle wichtigen Informationen zum technischen Ablauf der Prüfung haben Sie in den E-Mails vom 11.12.2019 und vom 08.01.2020 erhalten. Falls Sie diese nicht bekommen haben, dann wenden Sie sich bitte an Johannes Lengler.

Für die schriftliche Prüfung sind die grundlegenden Regeln ausserdem auf diesem Anweisungsblatt zusammengefasst. Für den Programmierteil wird Ihnen diese Java-Dokumentation zur Verfügung stehen (Zugriff aus dem ETH-Netz). Ausserdem wird Ihnen an Ihrem Platz eine Schritt-für-Schritt-Anleitung zum Einloggen zur Verfügung stehen. Sie können sie schon hier (endgültige Version) einsehen. Wir empfehlen Ihnen, die Anleitung vor der Klausur achon einmal anzuschauen.