Department of Computer Science | Institute of Theoretical Computer Science

CADMO - Center for Algorithms, Discrete Mathematics and Optimization

klausur_winter_2016.pdf

Algorithmen und Komplexität (D-MATH)

Dozierende

Prof. Dr. Angelika Steger, Dr. Johannes Lengler

Übungsleitung

Florian Meier

Zeit und Ort

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

Die Vorlesung beginnt am 18. September 2018. Die ersten Übungsstunden finden am 27. September statt.

Übungsgruppen

Die Übungen finden jeweils am Donnerstag von 16:15 bis 17:00 im Zentrum statt. Die Einteilung erfolgt alphabetisch per Nachnamen und kann sich bis am Sonntag der ersten Vorlesungswochen noch leicht ändern.

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, da der Lernerfolg positiv mit aktivem Lösen der Übungsaufgaben korreliert. Die Übungsaufgaben werden jeweils am Dienstag nach der Vorlesung online gestellt und werden ein Woche später in der Vorlesung abgegeben (Falls Sie verhindert sind die Vorlesung zu besuchen, geben Sie ihre Lösung einem Mitstudenten mit oder legen sie bis Dienstag 8 Uhr ins Fächlein vor dem Büro CAB G19.1). Die Übungsblätter bestehen jeweils aus drei Aufgaben. Zwei davon werden von den Assistenten eine davon von einem/einer Mitstudenten/in korrigiert. Zusätzlich steht die Musterlösung zur Selbstkorrektur jeweils ab Dienstag nach der Vorlesung zur Verfügung. Die korrigierten Übungsaufgaben werden am darauf folgendem Donnerstag in der Übungsstunde zurückgegeben. Wir empfehlen Ihnen die Möglichkeit des Peer-gradings zu nutzen, da sich dadurch die Qualität der eigenen Aufschriebe erfahrungsgemäss stark verbessert. Genauere Informationen und Hinweise zum Peer-Grading gibts hier.

15 Minuten Gespräche mit Assistenten

Zusätzlich zu den Übungsbetrieb stehen jedem Studenten drei 15 minütige Gespräche mit einem Assistenten zu. Die Studierenden präsentieren dabei die Grundideen einer Übungsaufgabe oder eines in der Vorlesung behandelten Themas und erhalten wertvolles, mündliches Feedback vom Assistenten. Nutzen Sie diese Möglichkeit. Zusätzlich wird eine intensive Ausseinandersetzung mit einem Thema gefördert und Ihre Präsentationskompetenz gestärkt. Jedes der drei Gespräche findet innerhalb eines vierwöchigen Zeitfensters (Anfangs, Mitte und Ende Semester) statt. Melden Sie sich für einen Zeitslot auf https://pele.ethz.ch/ an. Die Meetings finden jeweils montags 16:15-17:15, donnerstags 17:15 - 18:00 und freitags 12:15-13:15 statt, startend am Donnerstag 4. Oktober. Es ist auch möglich sich zu zweit für einen 30 Minuten Slot anzumelden. Für die Assistentengespräche kann eines der folgenden Themen gewählt werden, welches während den letzten 3 Wochen in der Vorlesung oder in den Übungen behandelt wurde:

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. Lösungen bitte bei Pascal Su per Email oder persöhnlich abgeben.

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