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

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 )

Blatt5

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)