Department of Computer Science | Institute of Theoretical Computer Science
Department of Computer Science | Institute of Theoretical Computer Science
Herbstsemester 2017, ETH Zürich
| Dozenten: |
Prof. Peter Widmayer Prof. Markus Püschel Prof. David Steurer |
| Vorlesung: | Donnerstag, 10:00 - 12:00 Uhr und 13:00 - 14:00 Uhr (jeweils in ML D28 und ML E12) |
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.
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 |
|---|---|---|
| 21.09.2017 | Einführung. Algorithmenentwurf. Stabiles Heiraten.
|
Folien: Algorithmen in realen Anwendungen Stabiles Heiraten Stabiles Heiraten (Beispiel) Links: Multiplicative Weights Method Video: Evolution and Computation (nicht prüfungsrelevant) |
| 28.09.2017 | Graphentheorie.
|
Folien: Graphentheorie Handgeschriebene Notizen: Graphentheorie Optionale Referenzen (Skript): 1.4.2, 1.4.2, 1.4.3, 5.1.1, 5.1.2 |
| 05.10.2017 | Graphenalgorithmen I.
|
Folien: Graphenalgorithmen I Handgeschriebene Notizen: Graphenalgorithmen I Optionale Referenzen (Skript): 1.3.1, 1.3.2, 5.1.3 |
| 12.10.2017 | Graphenalgorithmen II.
|
Folien: Graphenalgorithmen II Handgeschriebene Notizen: Graphenalgorithmen II Optionale Referenzen (Skript): 5.2, 5.3 |
| 19.10.2017 |
Maximum Subarray Sum Problem.
|
Handgeschriebene Notizen: Maximum Subarray Sum Problem. Optionale Referenzen (Skript): Maximum Subarray Sum: 1.5 Einheitskostenmodell: 1.3 (Die Terminologie ist ein bisschen anders) |
| 26.10.2017 |
Suchen und Sortieren I.
|
Material (Skript): von 2.1. bis 2.4 Handgeschriebene Notizen (nicht vollständig): Suchen und Sortieren I. Video: Amazing Crabs Shell Exchange |
| 2.11.2017 |
Suchen und Sortieren II.
|
Material (Skript): von 2.5. bis 2.7 (Randomisiertes Quicksort ist nicht relevant und wird im nächsten Semester gelehrt.) |
| 9.11.2017 |
Suchen und Sortieren III.
|
Material: Buch (Median): 3.1 Skript (Dynamische Programmierung): von 3.1 bis 3.3 |
| 16.11.2017 |
Dynamische Programmierung II.
|
Material (Skript): von 3.4 bis 3.6 |
| 23.11.2017 |
Dynamische Programmierung III.
|
Material (Skript): 3.7 Handgeschriebene Notizen: Rundreiseproblem. Link: Dynamische Programmierung. |
| 30.11.2017 |
Datenstrukturen I.
|
Material (Skript): 4.1, 4.4, 4.5 Handgeschriebene Notizen: Datenstrukturen I. |
| 7.12.2017 | Graphenalgorithmen III: Kürzeste Wege
|
Material (Skript): 5.5.1, 5.5.2, 5.5.3, Handgeschriebene Notizen: Kürzeste Wege |
| 14.12.2017 | Graphenalgorithmen IV:
|
Kürzeste Wege: Skript: 5.5.4 Minimale Spannbäume: Buch: 9.6 Handgeschriebene Notizen: Graphenalgorithmen IV |
| 21.12.2017 | Graphenalgorithmen V: Minimale Spannbäume
|
Buch: Union-Find-Strukturen: 6.2 Minimale Spannbäume: 9.6 Handgeschriebene Notizen: Graphenalgorithmen V |
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.
Weitere Literatur
Die Übungen finden jeweils am Montag von 9:00 bis 12:00 Uhr statt.
Verantwortlich für die Organisation der Übungen ist Chih-Hung Liu, CAB H33.1.
Erster Übungstermin ist Montag, der 25. September.
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.
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 (von zwei bis drei 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 bis drei Personen zugeteilt. Die Gruppen werden im Laufe des Semesters mehrmals neu eingeteilt.
In der Übungsstunde werden die Aufgaben besprochen. Anschliessend wird die eingereichte Lösung einer Gruppe von einer anderen Gruppe bewertet und mit Kommentaren 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.
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.
Sowohl für das Lösen eines Übungsblattes als auch für die Korrektur während der Übungsstunde können Bonuspunkte erarbeitet werden. 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 der zweiten Semesterhälfte können Sie weitere Bonuspunkte für das Lösen der Programmieraufgaben erlangen.
Am Ende des Semesters wird aus den Bonuspunkten eine Note für die Übungen berechnet. Die Note für die Übungen fliesst in die Endnote ein, sofern deren Berücksichtigung vorteilhaft ist. Die Endnote ist das Maximum aus der Note der Sessionsprüfung und dem gewichteten Mittel der Note für die Übungen (30%) und der Note der Sessionsprüfung (70%).