Theoretische Informatik (Kernfach)

(37-402 Theoretische Informatik-K, 3V2U, 8 Kreditpunkte)
Sommer 2004

Dozenten: Jiří Matoušek (IFW B 48.1), Emo Welzl (IFW B 49.2)
Chefassistent: Ingo Schurr / Robert Berke (IFW B 43)
Termine: Montag 9:00-10:00, Donnerstag 14:00-16:00, IFW A 36

Inhalte: Fortgeschrittene Entwurfs- und Analysemethoden für Algorithmen und Datenstrukturen; Komplexitätstheorie.
(Die Vorlesung wird im Vergleich zu den Vorjahren inhaltlich neu konzipiert.)

Sprache: Deutsch und englisch.

News: Unterlagen zur Vorlesung Komplexitätstheorie online erhätlich (kein Prüfungsstoff)

Inhalt

Die Inhalte im Einzelnen:

Random(ized) Search Trees (Emo Welzl)
- Mo., 29. März:
  Definitions. Depth of the smallest key.
- Do., 1. April
  Depth of smallest key (cont'd). Overall depth. Height.
- Mo., 5. April
  Depth of individual keys. Quicksort.
- Mo, 26. April
  Treaps.
- Do., 29. April
  Choosing the priorities in a treap. Range Search Trees.
Network Flows (Jiří Matoušek)
- Do., 8. April
  Definitions (network, flow, cut), max-flow-min-cut theorem
- Do., 15. April
  Ford-Fulkerson algorithm, capacity scaling, residual network, Dinitz algorithm
- Mo., 19. April
  Dinitz alg. (cont'd). Historical remarks. LP-formulation.
- Do., 22. April
  Bipartite matchings. Hall's Marriage Theorem.
Minimum Cut (Jiří Matoušek)
- Do., 22. April
  Introduction.
- Do., 29. April
  Karger's min-cut-algorithm.
- Mo., 3. Mai
  Algorithm by Karger and Stein.
- Do., 6. Mai
  Algorithm by Karger and Stein (cont'd).
Randomized Algebraic Algorithms (Jiří Matoušek)
- Do., 6. Mai
  Checking matrix multiplication. Checking if polynomial is identically zero.
- Mo., 10. Mai
  Perfect bipartite matching. The permanent.
- Do., 13. Mai
  Perfect bipartite matching (cont'd). Tutte matrix.
Randomized Rounding (Jiří Matoušek)
- Mo., 17. Mai
  Linear and Integer Linear Programming. Maximum Matching.
- Mo., 24. Mai
  Maximum independent set. Linear relaxation. Concentration for sums of ind. variables.
- Do., 27. Mai
  Concentration for sums of ind. variables (cont'd). Central Limit Theorem. Approximate Packing.
- Do., 3. Juni
  Approximate Packing (cont'd).
Point Location (Emo Welzl)
- Do., 3. Juni
  Point/Line Relative to a Convex Polygon. Line Relative to Point Set
- Mo., 7. Juni
  Line Relative to Point Set (Reporting).
- Do., 10. Juni
  Line Relative to Point Set (Counting). Planar Point Location (Point in Polytope).
- Mo., 14. Juni
  Planar Point Location (Counting Points Below Plane, Post Office Problem). Randomized Incremental Constructions, History Graph.
- Do., 17. Juni
  Trapezoidal Decomposition.
Visual Cryptography (Jiří Matoušek)
- Do., 17. Juni
  Introduction. 2 out of 2 schemes
- Mo., 21. Juni
  n out of n schemes. 2 out of n schemes.
- Mo., 28. Juni
  2 out of n schemes (cont'd). Hadamard matrices.
Complexity Theory (Markus Bläser)
- Do., 24. Juni
  Introduction to Complexity Theory (Crashcourse (PDF)).

Zu einzelnen Themen werden Unterlagen in der Vorlesung ausgegeben. Kopien der Unterlagen sind erhältlich in der Vorlesung oder bei Ingo Schurr / Robert Berke, IFW B43.
Bisher ausgegebene Unterlagen:

Random(ized) Search Trees (Seiten 1-19 am 29.03., Seiten 19-23 am 05.04., Seiten 23-30 am 26.04.)
Network Flows (Seiten 1-8 am 08.04., Seiten 8-17 am 15.04.)
Minimum Cut (Seiten 17-24 am 29.04.)
Randomized Algebraic Algorithms (Seiten 25-32 am 06.05.)
Randomized Rounding (Seiten 33-36 am 13.05.)
Point Location (Seiten 1-8 am 03.06., Seiten 9-12 am 07.06 und Seiten 13-16 am 10.06, Seiten, 16-25 am 01.07.)
Visual Cryptography (Seiten 42-51 am 24.06.)
Musterlösungen zu Aufgaben 1.4 - 1.7, 1.12, 1.14 (05.04.) 1.15-1.19, 1.23, 1.26, 1.27, 1.29 (19.04.); 3 - 5, Set 3 und zu Set 4 (29.04.); Set 5 (06.05.); Set 6 und Set 7 (03.06.); Set 8 (10.06.); Set 9 und Set 10 (17.06.); Set 11, Set 12 und Set 13 (01.07.);

Literatur: Die Vorlesung folgt keinem Lehrbuch. Das im Vorlesungsverzeichnis genannte Buch Introduction to Algorithms von T. H. Cormen, C. E. Leiserson, R. L. Rivest deckt weder alle Themen der Vorlesung ab noch deckt die Vorlesung alle Themen des Buches ab. Das Buch Randomized Algorithms von R. Motwani und P. Raghavan liefert eine gute Übersicht ueber randomisierte Verfahren. Computational Geometry -- Algorithms and Applications von M. de Berg, M. van Kreveld, M. Overmars und O. Schwarzkopf behandelt Themen aus der algorithmischen Geometrie, wie sie im Kapitel über Point Location vorgestellt wurden.

Errata:

Random(ized) Search Trees, Seite 16, Fussnote 8:
E[X+Y] = E[X] + E[Y] (statt E[X+Y]=E[X+Y])
Random(ized) Search Trees, Seite 18, Aufgabe 1.26 (1):
D⁽ⁱ⁾_n (statt D_i)
Random(ized) Search Trees, Seite 25, zweite Zeile:
if Q = ∅ (statt S = ∅)
Random(ized) Search Trees, Seite 27, letzte Zeile:
1/(j-k+1))=1 - 1/j (statt "1/(j-k+1))1 - 1/j" )
Network Flows, Seite 4,viertletzte Zeile:
val(f) (statt val(S))
Network Flows, Seite 5, letzte Zeile:
f'(e) (statt f')
Network Flows, Seite 6, 3. Zeile:
∑f'(s,x)-∑f'(x,s) (statt ∑f'(z,x)-∑f'(x,z))
Network Flows, Seite 6, Beweis der Proposition 1.9, Linie 5 vor Ende des Beweises:
be reached by a non-saturated path (statt: be reached by a saturated path)
Network Flows, Seite 7, 1. Zeile unter Bild:
algorithm needs 2000 steps! (statt: 1000 steps)
Network Flows, Seite 16, Bild:
I statt A, X statt B.
Network Flows, Seite 17, Bild:
I statt A, X statt B.
Network Flows, Seite 17, vorletzte Zeile des Beweises:
|I|-|J|+|N_J|≥|I| (statt |I|-|J|-|N_J|≥|I|)
Minimum Cut, Seite 20, Alg. GuessMinCut:
downto 3 (statt downto 2).
Minimum Cut, Seite 22, Alg. Cotract:
downto t+1 (statt downto t).
Minimum Cut, Seite 23
Ersetze 9 durch 16.
Point Location, Seite 2, Zeile 5:
that this a is not unique (statt that this x is not unique).
Point Location, Seite 8, Zeile 13:
n_i := |S_i| (statt n_i := |S_i+1|).
Point Location, Seite 4, Fussnote
See exercise 2.4 (statt See exercise 2.3).
Point Location, Seite 10, Zeile unter Bild
Figure 2.3: Three points and two lines (statt Figure 2.3: Two points and three lines).
Visual Cryptography:
Chapter 5 (statt Chapter 4).

Übungen

Die Übungsaufgaben werden in der Regel Donnerstags in der Vorlesung bekanntgegeben. Lösungsvorschläge sind in der darauffolgenden Woche in der Vorlesung am Donnerstag abzugeben.

Gestellt am 29.03., Abgabe: 01.04. (!)
In den Unterlagen zu Random(ized) Search Trees Aufgaben 1.4, 1.5, 1.7 und 1.14
Gestellt am 01.04., Abgabe: 08.04.
In den Unterlagen zu Random(ized) Search Trees Aufgaben 1.15, 1.17, 1.19 und 1.29
Gestellt am 08.04., Abgabe: 15.04.: Aufgaben-Blatt (PDF)
Gestellt am 15.04., Abgabe: 22.04.: Aufgaben-Blatt (PDF)
Gestellt am 22.04., Abgabe: 29.04.: Aufgaben-Blatt (PDF)
Gestellt am 29.04., Abgabe: 06.05.: Aufgaben-Blatt (PDF)
Gestellt am 06.05., Abgabe: 13.05.: Aufgaben-Blatt (PDF)
Gestellt am 13.05., Abgabe: 27.05.: Aufgaben-Blatt (PDF)
Gestellt am 27.05., Abgabe: 03.06.: Aufgaben-Blatt (PDF)
Gestellt am 03.06., Abgabe: 10.06.: Aufgaben-Blatt (PDF)
Gestellt am 10.06., Abgabe: 17.06.:
In den Unterlagen zu Point Location Aufgaben 2.5, 2.11, 2.12 und 2.9
Gestellt am 17.06., Abgabe: 24.06.: Aufgaben-Blatt (PDF)
Gestellt am 24.06., Abgabe: 01.07.: Aufgaben-Blatt (PDF)

Organisatorisches

Prüfungen

Semesterzwischenprüfung: Freitag, 30. April in den Übungen. Schriftliche Prüfung, 1 Stunde.
Endprüfung: Herbst, in der Prüfungssession. Schriftliche Prüfung, 3 Stunden.
In beiden Prüfungen sind keine Hilfsmittel (weder schriftlicher noch elektronischer Art) erlaubt!

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

Für Mathematiker gilt die Semesterzwischenprüfung als Testatsbedingung.

Übungsgruppen

Eine rege und regelmässige Teilnahme an den Übungsgruppen sowie eigenständige Bearbeitung der Übungen wird empfohlen!

Folgende Übungsgruppen werden angeboten:

Nr.	Zeit	Ort	Assistent
1	Fr., 8:00-10:00	HG F 26.3	Robert Berke / Ingo Schurr
2	Fr., 8:00-10:00	HG E 21	Marc Nunkesser
3	Fr., 8:00-10:00	HG G 26.5	Birgitta Weber
4	Fr., 8:00-10:00	LFW C 11	Leo Rüst
5	Fr., 8:00-10:00	ML F 40	Yoshio Okamoto
6	Fr., 10:00-12:00	HG G 3	Leon Peeters
7	Fr., 10:00-12:00	HG F 26.3	Robert Berke / Ingo Schurr

Die Übungen von Robert Berke und Ingo Schurr werden in der ersten Hälfte des Semesters von Ingo Schurr und in der zweiten Hälfte von Robert Berke betreut.
Die Übung von Yoshio Okamoto wird auf englisch abgehalten.

Theory of Combinatorial Algorithms