Department of Computer Science | Institute of Theoretical Computer Science

CADMO - Center for Algorithms, Discrete Mathematics and Optimization



Algorithmen und Komplexität (D-MATH)

Dozierende

Prof. Dr. Angelika Steger

Übungsleitung

Ralph Keusch, Florian Meier

Zeit und Ort

Dienstag 8:15 - 10:00, HG D 1.2

Die Vorlesung beginnt am 19. September 2017. Die ersten Übungsstunden finden am 28. September statt.

Übungsgruppen

Die Übungen finden jeweils am Donnerstag von 16:15 bis 17:00 im Zentrum statt. Melden Sie sich bis spätestens Montag, 25. September, auf echo.ethz.ch für eine Übungsgruppe an. Ein späterer Wechsel ist in der Regel nicht möglich. Die Anmeldung zu einer Übungsstunde funktioniert nur, wenn Sie die Vorlesung in myStudies belegt haben.

Inhalt

Die Vorlesung behandelt den Entwurf und die Analyse von Algorithmen und Datenstrukturen. Themengebiete sind:

Übungsblätter

Die Bearbeitung der Serien ist nicht verpflichtend. Wir empfehlen Ihnen trotzdem dringend, die Übungen schon während des Semesters zu lösen. Beachten Sie, dass dies die einzige Möglichkeit ist, direktes Feedback zu erhalten. Pro Serie werden von der Übungsleitung jeweils zwei Aufgaben ausgewählt, die bei allen Abgaben korrigiert werden. Diese beiden Aufgaben werden auf der Serie jeweils angegeben. Für die anderen Aufgaben steht jeweils die Musterlösung zur Selbstkorrektur zur Verfügung. Die Übungsaufgaben werden jeweils am Dienstag in der Vorlesung verteilt und in der anschliessenden Übungsstunde vorbesprochen. (Die erste Serie wird nicht vorbesprochen.) Die Serien können dann jeweils in der nächsten Vorlesung abgegeben werden.

Challenge-Aufgaben

Die erste korrekte Lösung gewinnt einen Bücherpreis! Die nächsten 5 korrekten Lösungen werden mit einer feinen Tafel Schokolade belohnt. Zudem verdient sich jeder, der eine korrekte Lösung findet, einen Platz in der Liste der gewieften Challenge-Aufgaben Bezwinger.

Slides

Die Slides der Vorlesung werden jeweils dienstags nach der Vorlesung online gestellt.

Zusätzliche Animationen von Algorithmen können auf vielen Webseiten im Internet gefunden werden. z.B. auf http://visualgo.net/.

Vorlesungsunterlagen

Prüfung

Die Prüfung ist schriftlich und dauert 120 Minuten. Sie findet während der Prüfungssession im Winter statt. Als Hilfsmittel dürfen 10 (beidseitig) handgeschriebene DIN A4 Blätter verwendet werden. Für die Prüfungsvorbereitung stellen wir die folgenden Testklausuren zur Verfügung:

Die folgenden Abschnitte aus dem Skript gehören nicht zum Prüfungsstoff:

Literatur

T. Cormen, C. Leiserson, R. Rivest:
Introduction to Algorithms, MIT Press, 1990
H.J. Prömel, A. Steger:
The Steiner Tree Problem: A Tour Through Graphs, Algorithms and Complexity, Vieweg, 2002
R. Sedgewick:
Algorithmen in C++, Pearson, 2003
S Baase, A. van Gelder:
Computer Algorithms, Addison Wesley, 2000
G. Brassard, P. Bratley:
Fundamentals of Algorithms, Prentice Hall, 1996
J. Kleinberg, E. Tardos:
Algorithm Design, Addison Wesley, 2005
T. Ottmann , P. Widmayer:
Algorithmen und Datenstrukturen, Spektrum, 2002
S. Arora, B. Barak:
Computational Complexity, Cambridge University Press, 2009