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

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 1Blatt 2Blatt 3Blatt 4Blatt 5Blatt 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.
GruppeZeitRaumTutorBesprechung
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 )

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:

News

[Nov’18] Our paper on regret minimization has been accepted at AAAI 2019 (acceptance rate 16.2%)!

[Oct’18] Our paper on alternative route planning for bicycles has been accepted at ALENEX 2019!

[Apr’18] Martin has successfully defended his Ph.D. thesis. Congratulations!

[Jan’18] The journal version of our paper on k-hop path covers will receive a publication award from our university!

[Nov’17] Our paper on a theoretical explanation for several speed-up techniques for route computation has been accepted at AAAI 2018!

[Oct’17] Thomas’ paper on area preserving map simplification has been accepted at ALENEX 2018!

[May’17] Daniel’s and Martin’s paper on rational points on the unit sphere has been accepted at ISSAC 2017!

[Apr’17] Our paper on personalized route planning with dynamic approximation guarantees has been accepted at SEA 2017!

[Jan’17] Martin’s paper on map matching has been accepted at SIAM SDM 2017!

[Nov’16] Our paper on simultaneous maze solving has been accepted at AAAI 2017.

[Okt’16] Two papers, one on growing balls (!), the other on map simplification will be presented at ALENEX 2017.

[Sep’16] Our paper on Deducing Individual Driving Preferences has been accepted at the 24th ACM SIGSPATIAL GIS 2016.

[Feb’16] Our paper on placing loading stations for EVs has been accepted at ICAPS 2016.

[Jul’15] Paper about our GeoSearch Engine OSCAR at the 16th Int. Conf on Web Information Systems Engineering (WISE)!

[Jun’15] We feel very honored to have our VLDB’14 paper almost verbatimly reproduced in the ‘prestigous’ journal IJSETR, see here. Yeah! 😉

[Feb’15] We were lucky to receive a Google Research Award for research on personalized route planning!

[Sep’14] Our paper “On k-Path Covers and their Applications” has received a Best Paper Award at the 40th Int. Conference on Very Large Databases (VLDB) in Hangzhou (5 out of 139 accepted out of 695 submitted papers).

[Sep’14] Our paper on “Energy-efficient Routing: Taking Speed into Account” has received a Best Paper Award at the 37th German Conference on Artificial Intelligence (KI).

[Jul’14] Our paper “Placement of Loading Stations for Electric Vehicles: No Detours Necessary!” has received a Honorable Mention at the 28th AAAI Conference on Artificial Intelligence (AAAI) in Quebec City (5 nominated out of 398 accepted out of 1406 submitted papers).

[Mar’14] Our StuPro-Team has completed their great “SchulScheduler” project.

[Nov’13] Jochen has defended his PhD thesis and moved on to TomTom.

[Feb’13] Sabine has defended her PhD thesis (already in Dec’12) and received the INFOS award for best CS PhD thesis in 2012!

[Mar’12] Our paper Path Shapes - An Alternative Method for Map Matching and Fully Autonomous Self-Localization presented at GIS 2011 has received the Best Paper Award, also see the ACM SIGSPATIAL newsletter.