Klausur
Klausurergebnisse / -Einsicht:
Termin für die Einsicht ist der 11.09.2014, 14 Uhr. Raum: 0.124.
Update: Klausurnoten hängen jetzt aus.
Update: Die Ergebnisse der Nachklausur (Frühjahr 2015) hängen nun aus. Die Klausureinsicht findet am Freitag den 20.03. von 9:30 bis 10:40 in Raum 1.168 statt.
Organisatorisches
- Dozent: Prof. Dr. Stefan Funke
- Übungen: Daniel Bahrdt, Thomas Mendel, Martin Seybold
Termine:
Zeit | Raum | Beginn | |
---|---|---|---|
Mo | 09:45-11:15 | V38.04 | 07.04.14 |
Di | 09:45-11:15 | V38.04 | 15.04.14 |
Montags: 7.4., 14.4, 28.4., 5.5., 12.5., 19.5., 26.5. , 2.6., 16.6., 23.6., 30.6., 7.7.
Dienstags: 15.4., 22.4., 29.4., 6.5., 13.5., 27.5. (MC-Test), 17.6. 15.7. (MC-Test)
Fragestunde: 27. August 15:00-16:00 Uhr im Anschluss an den 3. MC-Test
Themen:
- 7.4.: randAlg: Closest Pair
- 14.4.: randAlg: MinCut
- 15.4.: randAlg: MinCut; Las Vegas vs. Monte Carlo
- 22.4.: randAlg: MatrixMult-Check, Quicksort
- 28.4: randAlg: Concentration Bounds; zero Knowledge Proofs
- 29.4 randAlg: Streaming Algorithmen, sublineare Approximationsalgorithmen
- 5.5: randAlg: sublineares MST-Gewicht
- 6.5.: Hashing: Grundlagen
- 12.5.: Hashing: Universelles Hashing
- 13.5.: Hashing: Prefektes Hashing
- 19.5.: Skiplisten;
- 26.5.: NP-harte Graphprobleme: Vertex Cover
- 02.6.: Steiner-Baum
- 16.6.: TSP 2-APX und 1,5-APX
- 17.6.: TSP DynProg; Rucksack DynProg
- 23.6.: Rucksack (1+eps)-APX, CSP DynProg und (1+eps)-APX
- 30.6.: CSP (1+eps)-APX
- 07.7.: Shortest Path SpeedUp-Techniken: Contraction Hierarchies+Transit Nodes
Übersicht für die Klausur mit Ausschlüssen (!)
hier
Übungen
Anmeldung zu den Übungsgruppen: im eClaus
ab 11:20 am 14.4.
(Anmeldedaten werden in der Vorlesung bekannt gegeben)
Die Abgaben der Übungsaufgaben sind in Gruppen mit 2-3 Teilnehmern mit eClaus vorzunehmen. Abgaben von Programmcode bitte nur in C, C++, Ada oder Java.
Übungsblätter und Besprechungstermine
Blatt 1 | Blatt 2 | Blatt 3 | Blatt 4 | Blatt 5 | Blatt 6 | |||||
---|---|---|---|---|---|---|---|---|---|---|
Ausgabe | 09.04. | 25.04. | 09.05. | 23.05. | 13.06. | 27.06. | ||||
Abgabe | 18.04. | 02.05. | 16.05. | 30.05. | 20.06. | 04.07. | ||||
Gruppe | Zeit | Raum | Tutor | Besprechung | ||||||
1 | Mi 11:30–13:00 | 0.363 | Hartmann | 23.04. | 07.05. | 21.05. | 04.06. | 25.06. | 09.07. | |
2 | Mi 11:30–13:00 | 0.363 | Krumpe | 30.04. | 14.05. | 28.05. | 18.06. | 02.07. | 16.07. | |
3 | Mi 15:45–17:15 | 0.457 | Bahrdt/Mendel/Seybold | 23.04. | 07.05. | 21.05. | 04.06. | 25.06. | 09.07. | |
4 | Mi 15:45–17:15 | 0.457 | Hartmann | 30.04. | 14.05. | 28.05. | 18.06. | 02.07. | 16.07. | |
5 | Mi 15:45–17:15 | 0.463 | Hartmann | 23.04. | 07.05. | 21.05. | 04.06. | 25.06. | 09.07. | |
6 | Mi 15:45–17:15 | 0.463 | Krumpe | 30.04. | 14.05. | 28.05. | 18.06. | 02.07. | 16.07. | |
7 (WInfo) | Mi 17:30–19:00 | 0.363 | Hartmann | 23.04. | 07.05. | 21.05. | 04.06. | 25.06. | 09.07. | |
8 | Mi 17:30–19:00 | 0.363 | Krumpe | 30.04. | 14.05. | 28.05. | 18.06. | 02.07. | 16.07. |
Blatt1 (generator.tgz, instances.tgz)
Blatt2 (generator.tgz, instances.tgz) (Anm.: Bei Aufgabe 1 reicht es die Ungleichung für diskrete ZV zu beweisen.)
Blatt3 (klein.tgz, mittel.bz2, gross.bz2, sehr_gross.bz2) (Update: Tips für das Hashing, Knoten J in A5 entfernt)
Blatt4 (generator.tgz , instances.tgz )
Blatt6 (generator.tgz , instances.tgz )
Falls das gesuchte Blatt hier, zum erwarteten Zeitpunkt, nicht zu finden ist: versuchen Sie mal Ctrl-F5
Scheinbedingungen
Der Übungsschein ist als Studienleistung notwendige Voraussetzung, um zur Modulprüfung Algorithmik zugelassen zu werden. Notwendige Bedingung für den Übungsschein ist das Erreichen von 50% der Gesamtpunktzahl aller Übungen und das Präsentieren mindestens einer Lösung sowie das Bestehen von 2 MC-Tests.
Sie müssen in der Lage sein, jede Aufgabe die Sie oder Ihre Gruppe abgegeben haben, in den Übungen vorzurechnen. Sonst droht Punktabzug. Dies bedeutet insbesondere, dass Anwesenheitspflicht in der Übung herrscht.
MC-Tests
Probe-MC-Test findet sich hier (der echte Test wird etwas länger werden)
Ergebnisse vom 1. MC-Test (mit >=56% haben Sie bestanden).
Ergebnisse vom 2. MC-Test (mit >=53% haben Sie bestanden).
Ergebnisse vom 3. MC-Test (mit >=59% haben Sie bestanden).
Prüfungstermin: siehe LSF.
Literatur
Die Vorlesung folgt keinem Buch, allerdings schadet für das Verständnis sicher nicht, auch andere Quellen als die Vorlesung zur Nachbereitung heranzuziehen.
- T. Ottmann und P. Widmayer, Algorithmen 2004
- Thomas H. Cormen, Charles E. Leiserson, Introduction to Algorithms (Second Edition)
- R.Motwani P.Raghavan, Randomized Algorithms, 1995
Kurze Aufschriebe zu einzelnen Themen:
- Constrained Shortest Path (1+eps)-APX
- Contraction Hierarchies
- Transit Nodes (Originalpaper)