Algorithmen und Datenstrukturen

Herbstsemester 2018, 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.

Vorlesung

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

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

Datum	behandelte Themen	Unterlagen
20.09.2018	Einführung. Graphentheorie. Einführung, Organisation Graphentheoretische Konzepte Färbungen von Graphen Induktion	Folien: Einführung Graphentheorie 1 Graphen-Skript Optionale Referenzen (Skript): 1.4.1, 5.1.1, 5.1.2
27.09.2018	Graphentheorie. Induktion Gerichtete Graphen Zusammenhangskomponenten Topologisches Sortieren	Folien: Graphentheorie 2 Graphen-Skript Optionale Referenzen (Skript): 1.4.1, 5.1.1, 5.1.2, 5.3, 5.4
04.10.2018	Graphenalgorithmen. Gierige Knotenfärbung Star in der Menge Einheitskostenmodell O-Notation Graphenrepräsentation	Folien: Graphenalgorithmen 1 Graphen-Skript Optionale Referenzen (Skript): 1.2.2, 1.3, 5.1.3, 5.2
11.10.2018	Graphenalgorithmen. Topologische Sortierung mit Tiefensuche Kürzeste Wege mit Breitensuche	Folien: Graphenalgorithmen 2 Graphen-Skript Optionale Referenzen (Skript): 5.2-5.5
18.10.2018	Maximum Subarray Sum Problem. Problemdefinition Naiver Algorithmus, Präfixsummen vorberechnen, Divide-and-Conquer-Algorithmus, induktiver Algorithmus Untere Schranken, Problemkomplexität Einheitskostenmodell. O-Notation, Omega, Theta	Handgeschriebene Notizen: Vorlesung 5. (Update am 7.11.2018, 10:15 Uhr) Optionale Referenzen (Skript): Maximum Subarray Sum: 1.5 Einheitskostenmodell: 1.3 (Die Terminologie ist ein bisschen anders)
25.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	Handgeschriebene Notizen: Suchen und Sortieren I. (Update am 7.11.2018, 10:15 Uhr) Optionale Referenzen (Skript): von 2.1. bis 2.3
01.11.2018	Sortieren Heapsort, Heap, Priority Queue Mergesort Quicksort Untere Schranke Sortieren	Handgeschriebene Notizen: Sortieren II. Optionale Referenzen (Skript): von 2.4. bis 2.7
08.11.2018	Abstrakte Datentypen/Datenstrukturen Stapel Schlange Prioritätswarteschlange Suchbäume Natürliche Suchbäume AVL-Bäume Prioritätswarteschlange	Handgeschriebene Notizen: Datenstrukturen I. Optionale Referenzen (Skript): 4.1, 4.4, 4.5
15.11.2018	Dynamische Programmierung Längste aufsteigende Teilfolge Längste gemeinsame Teilfolge Editierdistanz Matrixmultiplikation	Handgeschriebene Notizen: Dynamische Programmierung I. Optionale Referenzen (Skript): 3.1-3.5
22.11.2018	Dynamische Programmierung. Matrixmultiplikation Teilsummenproblem (subset sum) Rucksackproblem (knapsack)	Folien: Dynamische Programmierung II. Optionale Referenzen (Skript): 3.5-3.7
29.11.2018	Dynamische Programmierung. Kürzeste Wege in Graphen mit allgemeinen Kantengewichten Algorithmus von Bellman und Ford Algorithmus von Floyd und Warshall	Folien: Dynamische Programmierung III. Optionale Referenzen (Skript): 5.5.3
06.12.2018	Minimale Spannbäume. Amortisierte Analyse. Algorithmus von Prim Algorithmus von Kruskal Union find	Folien: Minimale Spannbäume. Optionale Referenzen (Buch): Kapitel 9.3
13.12.2018	Kürzeste Wege. Algorithmus von Dijkstra Algorithmus von Johnson	Handgeschriebene Notizen: Kürzeste Wege II. Optionale Referenzen (Skript): 5.5
20.12.2018	Matrixmultiplikation und Auswahlproblem Algorithmus von Karatsuba und Ofman Algorithmus von Strassen Auswahlproblem	Handgeschriebene Notizen: Vorlesung 14. Optionale Referenzen (Skript): 1.3, 3.5

Literatur zur Vorlesung

Das Buch zur Vorlesung ist ''Algorithmen und Datenstrukturen'', T. Ottmann und P. Widmayer, 6. Auflage, Spektrum Verlag, 2017. Dieses können Sie bei der Polybuchhandlung beziehen oder innerhalb des ETH-Netzes als PDF-Datei herunterladen.

Aus vorherigen Vorlesungen gibt es ein Skript, das einen Grossteil des Stoffes behandelt. Dieses können Sie innerhalb des ETH-Netzes als PDF-Datei herunterladen.

NEU: Zu dieser Vorlesung gibt es neu auch ein Skript zur Graphentheorie. Dieses können Sie innerhalb des ETH-Netzes als PDF-Datei herunterladen.

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:00 bis 12:00 Uhr statt.
Verantwortlich für die Organisation der Übungen ist Barbara Geissmann, CAB H34.2.

Erster Übungstermin ist Montag, der 24. September.

Übungsblätter	Lösungen
Übungsblatt 0	Beispiellösung Blatt 0
Übungsblatt 1	Beispiellösung Blatt 1
Übungsblatt 2	Beispiellösung Blatt 2
Übungsblatt 3 Programmieraufgaben P3 Vorlage P3.1 Vorlage P3.2 Technische Anleitung Vorlage P3.0	Beispiellösung Blatt 3
Übungsblatt 4	Beispiellösung Blatt 4
Übungsblatt 5 Programmieraufgaben P5 Vorlage P5.1 Vorlage P5.2	Beispiellösung Blatt 5 Beispiellösung Programmieraufgaben P5
Übungsblatt 6	Beispiellösung Blatt 6
Übungsblatt 7 (Update: 6.11.2018, 18:20 Uhr) Programmieraufgaben P7 (Update: 13.11.2018, 09:10 Uhr) Vorlage P7.1 Vorlage P7.2	Beispiellösung Blatt 7 Beispiellösung Programmieraufgaben P7
Übungsblatt 8	Beispiellösung Blatt 8
Übungsblatt 9 Programmieraufgaben P9 Vorlage P9.1 Vorlage P9.2	Beispiellösung Blatt 9 Beispiellösung Programmieraufgaben P9
Übungsblatt 10	Beispiellösung Blatt 10
Übungsblatt 11 Programmieraufgaben P11 Vorlage P11.1 Vorlage P11.2	Beispiellösung Blatt 11 Beispiellösung Programmieraufgaben P11
Übungsblatt 12	Beispiellösung Blatt 12
KEIN Bonus. DENNOCH prüfungsrelevant. Übungsblatt 13 KEIN Bonus. Zum Üben. Programmieraufgaben P13 (Update, 25.12.2018, link bugfix) Vorlage P13.1 Vorlage P13.2 Vorlage P13.3 Vorlage P13.4	Beispiellösung Blatt 13 Beispiellösung Programmieraufgaben P13

Prüfung

Probeprüfung Vorlage
Klausur (deutsch) Exam (englisch) Vorlage P1 Vorlage P2	Beispiellösung (englisch)

Fragen und Kommentare

Sie können Ihre Fragen im Forum auf Moodle stellen. Wir werden Ihre Beiträge lesen und die Fragen direkt im Forum beantworten, sodass auch andere Studierende von den Antworten profitieren können.

Organisation und Ablauf der Übungen

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

Die wöchentlichen Übungsblätter sollen jeweils in Gruppen vo zwei Personen gelöst werden. Bitte geben Sie eine gemeinsame Lösung (für die Gruppe) in der darauffolgenden Woche vor dem Beginn Ihrer Übungsgruppe ab.

In der ersten Übungsstunde werden Sie einer Gruppe von zwei Personen zugeteilt. Die Gruppen werden im Laufe des Semesters mehrmals (alle 3 Wochen) neu eingeteilt. Die Einteilung erfolgt jeweils durch den Assistenten.

In der Übungsstunde 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 beim Assistenten abgegeben. Der Assistent wird sowohl das Blatt als auch die Korrektur bis zur darauffolgenden Übungsstunde bewerten. Wir werden ausserdem Beispiellösungen für alle Übungsblätter vorbereiten und auf dieser Webseite veröffentlichen.

Programmieraufgaben

Ab dem zweiten Monat im Semester gibt es zusätzlich auch Programmieraufgaben. Diese werden alleine (nicht in Gruppen) gelöst. Details dazu folgen. Die Programmieraufgaben werden online im sogenannten Judge abgegeben. Bei jeder Programmieraufgabe gibt es einen mit "Lösung einschicken / Submit solution" bezeichneten Link, mit dem der entsprechende Bereich des Judges erreicht werden kann.

Lösen Sie die Programmieraufgaben alleine (nicht in Gruppen). Die Programmieraufgaben werden online im sogenannten Judge abgegeben. Bei jeder Programmieraufgabe gibt es einen mit "Lösung einschicken / Submit solution" bezeichneten Link, mit dem der entsprechende Bereich des Judges erreicht werden kann. Bitte beachten Sie:

Jederzeit können Sie Ihre Fragen im Forum auf Moodle stellen.

• Die verwendete Programmiersprache ist Java.
• Lösungen dürfen nur eine Datei (.java) umfassen.
• Die Hauptklasse muss zwingend den Namen Main tragen, damit die Lösung vom Judge akzeptiert wird. Zudem darf sie nicht als public deklariert werden! In den Vorlagen wird die Hauptklasse bereits korrekt deklariert. Falls Sie die Vorlage nicht verwenden, deklarieren sie Ihre Hauptklasse wie folgt:
  class Main {
    public static void main(String[] args) { ... }
}
• Für jedes Problem werden Testinstanzen zur Verfügung gestellt, die vergleichbar mit den Instanzen auf dem Judge sind.
• Eingaben erfolgen grundsätzlich von der Standardeingabe. Die Vorlage importiert für Sie zum Einlesen der Eingabe von der Konsole die Klasse java.util.Scanner.
• Benutzen Sie die Funktion System.out.println zur Ausgabe.
• Sie können mehrmals Lösungen für dasselbe Problem einreichen.
• Der Judge benötigt einige Zeit zur Prüfung Ihrer Abgabe. Bitte schicken Sie Ihre Lösung daher nicht erst kurz vor Ende der Deadline ein.

Bonuspunkte

Sowohl für das Lösen eines Übungsblattes als auch fürs Peer Feedback während der Übungsstunde können Bonuspunkte erarbeitet werden, die punkterelevanten Aufgaben sind jeweils speziell markiert. Voraussetzung für das Erlangen von Bonuspunkten sind die Teilnahme an der Übungsgruppe sowie das gemeinsame Lösen und Abgeben des Übungsblattes und die Korrektur eines abgegebenen Übungsblattes in der Übungsstunde. In Verlauf des Semesters können Sie weitere Bonuspunkte für das Lösen der Programmieraufgaben erlangen.

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. Um den Maximalbonus zu erhalten sind mindestens 80% der Punkte erforderlich.

Prüfung und Note

Die Prüfung findet in der Prüfungssession statt. Sie dauert insgesamt 4 Stunden. Die Prüfung umfasst sowohl Theorieaufgaben (50%), die schriftlich auf Papier gelöst werden, als auch Programmieraufgaben (50%), die auf dem Judge eingereicht werden.

Die Endnote wird folgendermassen berechnet: Note aus der Sessionsprüfung + Bonusnote.