Department of Computer Science | Institute of Theoretical Computer Science
Department of Computer Science | Institute of Theoretical Computer Science
Herbstsemester 2016, ETH Zürich
| Dozenten: |
Prof. Peter Widmayer Prof. Markus Püschel |
| 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. Für Fragen und Kommentare haben wir ein Moodle-Forum eingerichtet.
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 |
|---|---|---|
| 22.09.2016 | Einführung. Algorithmenentwurf. Güte von Algorithmen.
|
Folien: Organisation Überblick Buch: Kapitel 1.1 Kapitel 1.2.3 (Multiplikation ganzer Zahlen) |
| 29.09.2016 | Mathematische Grundlagen.
|
Buch: Concrete Mathematics:
|
| 06.10.2016 | Maximum Subarray Sum Problem.
|
Buch: Kapitel 1.3 |
| 13.10.2016 | Suchen und Sortieren.
|
Buch: Kapitel 3.2 und 2.1 |
| 20.10.2016 | Sortieren II.
|
Buch: Kapitel 2.3 und 2.4 |
| 27.10.2016 | Sortieren III.
|
Buch: Kapitel 2.2 und 2.8 |
| 03.11.2016 | Dynamische Programmierung I.
|
Buch: Kapitel 1.2.3, 7.1 und 7.4 Cormen et al.: Kapitel 15 |
| 10.11.2016 | Dynamische Programmierung II.
|
Buch: Kapitel 7.2 und 7.3 |
| 17.11.2016 | Datenstrukturen für Wörterbücher I: Hashing, selbstanordnende lineare Listen.
|
Buch: Kapitel 1.5, 3.3, 4.1 bis 4.3.2, 4.3.4 |
| 24.11.2016 | Datenstrukturen für Wörterbücher II: Suchbäume.
|
Buch: Kapitel 5.1, 5.2.1 |
| 01.12.2016 | Graphenalgorithmen I.
|
Buch: Kapitel 9 (Anfang), 9.2.1 |
| 08.12.2016 | Graphenalgorithmen II.
|
Buch: Kapitel 9.1, 9.3, 9.4.1 |
| 13.12.2016 | Graphenalgorithmen III: Kürzeste Wege.
|
Buch: Kapitel 9.5 |
| 20.12.2016 | Graphenalgorithmen IV: Minimale Spannbäume (Vorschau).
|
Handgeschriebene Notizen: Graphenalgorithmen IV Buch: Kapitel 6.2 und 9.6 |
Das Skript zur Vorlesung (Stand: 15. Dezember 2017) können Sie unter diesem Link herunterladen.
Das Buch zur Vorlesung ist Algorithmen und Datenstrukturen, T. Ottmann und P. Widmayer, 5. Auflage, Spektrum Verlag, 2012. Dieses können Sie bei der Polybuchhandlung beziehen oder innerhalb des ETH-Netzes als PDF-Datei herunterladen.
Weitere Literatur
Die Übungen finden jeweils am Freitag von 13:00 bis 16:00 Uhr, beziehungsweise am Montag von 9:00 bis 12:00 Uhr statt.
Verantwortlich für die Organisation der Übungen ist Thomas Tschager, CAB H39.1.
Erster Übungstermin ist Freitag, der 23. September, beziehungsweise Montag, der 26. September.
Melden Sie sich bei Fragen zur Gruppeneinteilung bitte umgehend bei Thomas Tschager.
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 donnerstags nach der Vorlesung auf dieser Seite ein Übungsblatt veröffentlicht. Ab Woche 4 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 der Vorlesung um 10 Uhr im Eingangsbereich vor ML D28 ab.
In der ersten Übungsstunde werden Sie einer Gruppen 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 die Korrektur bis zur darauffolgenden Übungsstunde bewerten. Wir werden ausserdem Beispiellösungen für alle Übungsblätter vorbereiten und auf dieser Webseite veröffentlichen.
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 das gemeinsame Lösen und Abgeben des Übungsblattes sowie 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. Dabei werden die zwei schlechtesten Resultate in jeder Kategorie (Lösen, Korrigieren, Programmmieren) nicht berücksichtigt. 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%).
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:
Jeden Dienstag findet um 17:00 Uhr in der TI Bibliothek (CAB G 15.2) eine Fragestunde zu den Programmieraufgaben statt. Dort versuchen wir Fragen zur Aufgabenstellung, der Implementierung in Java und zum Online-Judge zu beantworten.
Jederzeit können Sie Ihre Fragen auch im Forum stellen (wenn möglich in englischer Sprache). class Main {
public static void main(String[] args) { ... }
}