Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Vorlesung Theoretische Informatik-K, 2005

Theoretische Informatik (Kernfach)

(251-0402-00 Theoretische Informatik-K, 3V2U, 8 Kreditpunkte, Sommer 2005)

Dozenten: Jiří Matoušek, Emo Welzl (CAB G15.2)
Chefassistenten:  Robert Berke (CAB G37.2), Leo Rüst (CAB G33.3)
Termine: Montag 9:15-10:00, Donnerstag 14:15-16:00, IFW A36
Sprache: Deutsch und Englisch
Inhalte: Fortgeschrittene Entwurfs- und Analysemethoden für Algorithmen und Datenstrukturen: Random(ized) Search Trees, Point Location, Network Flows, Minimum Cut, Randomized Algebraic Algorithms. Zudem eine Einführung in das PCP Theorem.
Literatur: Zu einzelnen Themen werden Unterlagen in der Vorlesung ausgegeben. Die folgenden Standardwerke decken weder alle Themen der Vorlesung ab noch deckt die Vorlesung alle Themen dieser Bücher ab.
  • Introduction to Algorithms von T. H. Cormen, C. E. Leiserson, R. L. Rivest
  • Randomized Algorithms von R. Motwani und P. Raghavan
  • Computational Geometry -- Algorithms and Applications von M. de Berg, M. van Kreveld, M. Overmars und O. Schwarzkopf

Prüfungen

Die Endnote setzt sich zu 25% aus der Note der Semesterzwischenprüfung und zu 75% aus der Note der Endprüfung zusammen.

In allen Fällen müssen Sie am Anfang des Semesters einen Chefassistenten entsprechend informieren.

Übungen

Die wöchentlichen Übungsserien sind in der Regel Donnerstags online verfügbar. Lösungsvorschläge sind in der darauffolgenden Woche in der Vorlesung am Donnerstag abzugeben. Eine rege und regelmässige Teilnahme in den Übungsgruppen sowie eigenständige Bearbeitung der Übungen wird empfohlen!

Erste Übung ist am Freitag, 1. April 2005. Auf diesen Termin müssen noch keine Übungsaufgaben gelöst werden.

Nr Gestellt am Abgabe am Aufgabenstellung Musterlösung
4 Seiten pro Blatt
Musterlösung
2 Seiten pro Blatt
1 31. März 7. April Übung1 Musterlösung1 Musterlösung1
2 7. April 14. April In den Unterlagen zu Random(ized) Search Trees Aufgaben 1.15, 1.17, 1.19 und 1.29 Musterlösung2 Musterlösung2
3 14. April 21. April In den Unterlagen zu Random(ized) Search Trees Aufgaben 1.26, 1.36, 1.37, 1.38 und 1.41 Musterlösung3 Musterlösung3
4 21. April 28. April In den Unterlagen zu Point Location Aufgaben 2.1, 2.3, 2.4 und 2.5 Musterlösung4 Musterlösung4
5 28. April 12. Mai In den Unterlagen zu Point Location Aufgaben 2.9, 2.11, 2.12, 2.15, 2.16 und 2.17 Musterlösung5 Musterlösung5
6 19. Mai 26. Mai Übung6 Musterlösung6 Musterlösung6
7 26. Mai 2. Juni Übung7 Musterlösung7 Musterlösung7
8 2. Juni 9. Juni Übung8 Musterlösung8 Musterlösung8
9 9. Juni 16. Juni Übung9 Musterlösung9 Musterlösung9
10 16. Juni 23. Juni Übung10 Musterlösung10 Musterlösung10
11 23. Juni 30. Juni Übung11 Musterlösung11 Musterlösung11

Übungsgruppen

Hier können Sie sich in eine der folgenden Übungsgruppen eintragen. Achtung: Der Zugriff auf den Link funktioniert aus Sicherheitsgründen nur innerhalb des ETH-Netzwerks (oder wenn eine VPN Verbindung mit dem ETH-Netzwerk besteht). Bei Problemen wenden Sie sich an Leo Rüst.

Nr.Zeit Ort Assistent
1 FR 8:15-10:00 HG E21 Robert Berke
2 FR 8:15-10:00 HG F26.3 Leo Rüst
3 FR 8:15-10:00 HG G26.5 Philipp Zumstein
4 FR 8:15-10:00 LFW C11 Dieter Mitsche
5 FR 10:15-12:00 HG F26.3 Birgitta Weber / Marc Nunkesser
6 FR 10:15-12:00 HG E1.2 Leon Peeters

Übungsgruppe 5 wird abwechselnd von Birgitta Weber bzw. Marc Nunkesser betreut.

Inhalt

Die Inhalte im Einzelnen: