Algorithms, Probability, and Computing
| Dozenten: |
Emo Welzl (CAB G15.2)
Angelika Steger (CAB H19.1)
Peter Widmayer (CAB H15)
|
| Chefassistenten: |
Philipp Zumstein (CAB G17) Patrick Traxler (CAB G38) |
| Termine: |
Montag 13:15-14:00 CAB G11, Dienstag 14:15-16:00, CAB G51, Vorlesungsbeginn: Dienstag, 24. Oktober 2006 |
| 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 (matchings), Probabilistically Checkable Proofs (introduction). |
| Literatur: |
Zu einzelnen Themen werden Unterlagen in der Vorlesung ausgegeben. Die Reading Assignments Basics of Probabilistic Analysis for the APC-Lecture sind elektronisch verfügbar. 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
Zusätzliche Literatur zum Kapitel 6, Probablistic Checkable Proofs: Wie man Beweise verifiziert, ohne sie zu lesen von A. Steger und H.J. Prömel in Higlights der Informatik (I. Wegener, ed.), Springer Verlag 1996
|
Prüfungen
- Semesterzwischenprüfung:
TERMIN: Mi 06. Dezember 2006, 16-17 (Beginn Punkt 16 Uhr!) ORT: HG D 7.1 STOFF: bis und mit 04. Dezember
Schriftliche Prüfung, keine Hilfsmittel (weder schriftlicher noch elektronischer Art) erlaubt.
Die Semesterzwischenprüfung der letztjährigen Vorlesung finden Sie hier. Beachten Sie, dass die Prüfung in der Prüfungssession keineswegs ähnlich (in Bezug auf Inhalt und Schwierigkeit) zur Zwischenprüfung sein muss.
- Endprüfung:
Prüfungseinsicht: in den ersten beiden Semesterwochen, CAB G 19.1
Schriftliche Prüfung in der Prüfungssession (3h), keine Hilfsmittel (weder schriftlicher noch elektronischer Art) erlaubt.
WANN: Donnerstag 01. März 2007, 9:00 - 12:00, HG E7
Stoffumfang: Skript Kapitel 1 bis 6
Die Prüfung vom letzten Jahr finden Sie hier. Beachten Sie, dass die diesjährige Prüfung keineswegs ähnlich zur letzten sein muss.
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 gelten neu, in Absprache mit dem Studiensekretariat,
die selben Regelungen wie für die Studenten aus D-INFK. Insbesondere
sind die Prüfungen schriftlich zu den angekündigten Terminen abzulegen, eine
Möglichkeit zur mündlichen Prüfung besteht nicht mehr. Für die Endprüfung
müssen Sie sich wie gewohnt (d.h. zusammen mit Ihrer Prüfungsanmeldung für die
Schlussdiplomprüfung Teil B) beim Mathematik Studiensekretariat anmelden.
-
Für Studenten die an der Semesterzwischenprüfung aus wichtigem Grund verhindert sind (Militärdienst, etc.), folgt 2 Wochen später die Gelegenheit diese nachzuholen (gemischt schrifltich / mündlich).
-
Auswärtige Studenten: Nehmen an der Semesterzwischenprüfung teil. Wenn Sie die Endprüfung in der Prüfungssession nicht wahrnehmen können, wird in der letzten oder vorletzten Semesterwoche eine Prüfung angeboten (gemischt schriftlich/mündlich).
-
ETH Studenten die im Herbst wegen Studium an Universitäten im (fernen) Ausland verhindert sind: Gemäss Reglement müssen Sie eine schriftliche Prüfung ablegen. Sie legen die Prüfung an ihrer Universität unter Aufsicht vor Ort zeitgleich mit der Prüfung an der ETH ab.
In allen Fällen müssen Sie am Anfang des Semesters einen Chefassistenten entsprechend informieren.
Übungen
Die wöchentlichen Übungsserien sind in der Regel Dienstags online verfügbar.
Lösungsvorschläge sind in der darauffolgenden Woche in der Vorlesung am
Dienstag abzugeben. Eine rege und regelmässige Teilnahme in den Übungsgruppen
sowie eigenständige Bearbeitung der Übungen wird empfohlen!
Erste Übungsstunde ist am 25., 26. bzw. 27. Oktober.
Übungensstunden vor Weihnachten (20., 21. und 22. Dezember) fallen aus, dafür gibt es in der ersten Januar-Woche bereits Übungsstunden.
| Nr |
Gestellt am |
Abgabe am |
Aufgabenstellung |
Musterlösung
4 Seiten pro Blatt |
Musterlösung
2 Seiten pro Blatt |
| 0 |
06. April |
- |
Präsenzaufgaben für die erste Übungsstunde |
Musterlösung0 |
Musterlösung0 |
| 1 |
24. Oktober |
31. Oktober |
Übung1
1.4, 1.5, 1.7, and 1.14 in the hand-out Random(ized) Search Trees |
Musterlösung1 |
Musterlösung1 |
| 2 |
31. Oktober |
7. November |
1.15, 1.17, 1.19, 1.26, and 1.30 in the hand-out Random(ized) Search Trees |
Musterlösung2 |
Musterlösung2 |
¨
| 3 |
07. November |
14. November |
1.29, 1.36, 1.39, 1.44, and 1.45 in the hand-out Random(ized) Search Trees |
Musterlösung3 |
Musterlösung3 |
| 4 |
14. November |
21. November |
2.1, 2.2, 2.3, 2.4, and 2.5 in the hand-out Point Location |
Musterlösung4 |
Musterlösung4 |
| 5 |
21. November |
28. November |
2.9, 2.11, 2.15, 2.16, and 2.17 in the hand-out Point Location |
Musterlösung5 |
Musterlösung5 |
| 6 |
28. November |
05. Dezember |
Übung6 |
Musterlösung6 |
Musterlösung6 |
| 7 |
05. Dezember |
12. Dezember |
Übung7 |
Musterlösung7 |
Musterlösung7 |
| 8 |
12. Dezember |
19. Dezember |
Übung8 |
Musterlösung8 |
Musterlösung8 |
|
|
|
Class exercises |
Musterlösung |
Musterlösung |
| 9 |
09. Januar |
16. Januar |
Übung9 |
Musterlösung9 |
Musterlösung9 |
| 10 |
16. Januar |
23. Januar |
Übung10 |
Musterlösung10 |
Musterlösung10 |
| 11 |
23. Januar |
30. Januar |
Übung11 |
Musterlösung11 |
Musterlösung11 |
Übungsgruppen
Errata zum Skript
- Chapter 5, page 4, Exercise 5.1. The condition must correctly say "in case matrix C is wrong in exactly one row" cf Exercise 9.1.
- Chapter 5, page 7, Exercise 5.4. d <= |S|
- On page 29, chapter 6, in the proof of the consistency test, where we
do this tensor product manipulation, we get to the
point where we write some expressions as
u_i0 v_j0 + S
(lower half of page), where we say that S does not depend on
u_i0 and v_j0. That is the part which is wrong. S has all kinds
of terms that depend either on u_i0 or v_j0 (none that
depend on both that's right). The way out, is to write for (A,B,D) in GF(2)
(independent of u_i0 and v_j0):
u_i0 A + v_j0 B + u_i0 v_j0 + D.
Now:
if D=1, we get 1 for u_i0 = v_j0=0
if D=0 and A = 1, we get 1 for u_i0 = 1, v_j0 = 0
if D=0 and B = 1, , we get 1 for u_i0 = 0, v_j0 = 1
if D=0, A=0, and B=0, we get 1 for u_i0 = v_j0 = 1
so in any case, we get 1 with probability at least 1/4 as required.
Inhalt
- Random(ized) Search Trees [EW]
- DI, 24. Oktober [EW]
Overview of the course. Introduction and Definitions. Depth of the smallest key.
- MO, 30. Oktober [EW]
Overall Depth. Expected Height.
- DI, 31. Oktober [AS]
Expected Height (cont'd). Depth of Individual Keys. Quicksort.
- MO, 6. November [EW]
Quickselect. Randomized Search Trees: Def. of Treaps, Insertions.
- DI, 7. November [EW]
Treaps (cont'd). Random real numbers. Range trees.
- Point Location [EW]
- MO, 13. November [PW]
2-dimensional range queries: fractional cascading. Nearest point: locus approach.
- DI, 14. November [PW]
Point/Line relative to a convex polygon. Line relative to a convex polygon (reporting, duality) [PW]
- MO, 20. November [EW]
Closest point in the plane (Post Office Problem). Trapezoidal decomposition.
- DI, 21. November [EW]
Trapezoidal decomposition (cont'd).
- Maximum Flow [PW]
- MO, 27. November [PW]
Residual graph and augmenting path. Ford-Fulkerson algorithm.
- DI, 28. November [PW]
Proof of the Main Theorem. Capacity Scaling.
- MO, 4. Dezember [PW]
Capacity scaling cont'd (running time analysis).
- DI, 5. Dezember [PW]
Shortest Augmenting Paths. Dinits Algorithm. Other Maxflow Algorithms.
- MI, 6. Dezember: Zwischenprüfung
- MO, 11. Dezember [PW]
Bipartite matchings. Hall's Theorem.
- Minimum Cut [AS]
- DI, 12. Dezember [AS]
Introduction. Random Contractions.
- MO, 18. Dezember [AS]
Bootstrapping.
- Randomized Algebraic Algorithms [EW]
- DI, 19. Dezember [EW]
Checking Matrix Multiplication. Polynomial Identity Test. Testing for Perfect Bipartite Matchings.
- Weihnachtsferien: SA 23. Dezember bis DI 02. Januar
MO 01. Januar und DI 02. Januar finden noch keine Vorlesungen statt!
- MO, 8. Januar [EW]
Perfect Matchings in General Graphs. Comparison with Other Matching Algorithms.
Introduction to PCP
- DI, 9. Januar [AS]
Probabilistic Checkable Proofs. Equivalence of Inapproximability and PCP (one way).
- MO, 15. Januar [AS]
Equivalence of Inapproximability and PCP (the other way).
- DI, 16. Januar [EW]
Linearity Testing.
- MO, 22. Januar [EW]
Linearity Testing (cont'd).
- DI, 23. Januar [EW]
Safe Evaluation. Proof of Baby PCP.
- MO, 30. Januar [AS]
Hardness of Approximation. FPTAS, PTAS, APX.
- DI, 31. Januar [AS]
Hardness of MAX3SAT. AP-Reductions. APX-Hardness of MAX2SAT.
- Semesterende FR 02. Februar
