Department of Computer Science | Institute of Theoretical Computer Science

CADMO - Center for Algorithms, Discrete Mathematics and Optimization

Algorithmen und Datenstrukturen

Herbstsemester 2019, ETH Zürich

Dozenten: Markus Püschel
David Steurer
Organisation: Johannes Lengler
Vorlesung: Donnerstag, 10:15 - 12:00 Uhr und 13:15 - 14:00 Uhr (in ML D28 mit Video-Übertragung in ML E12)
Übungen: Montag, 9:15 - 12:00 Uhr, davon 11-12 Uhr betreutes Arbeiten

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:

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
Vorlesungnotizen
Optionale Referenzen (Skript):
4.1, 4.4, 4.5

14.11.2019 Graphen
  • Einführung Graphen
  • Eulertouren
  • Datenstrukturen von Graphen I
Optionale Referenzen (Skript):
5.1.1, 5.1.2

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. Das Skript zur Graphentheorie wird im Laufe des Semesters freigeschaltet. 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

Ü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
Programmieraufgaben P9
Vorlage P9.1
Vorlage P9.2

Vorlage P9.3 (no bonus points, just for practise)

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

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.