max planck institut
informatik

# Teaching

## Algorithms and Data Structures (WS 09/10)

Time: Monday and Wednesday, 12-14
Room: Building E1.3, Room HS001 (on 07.12. and 03.02. in HS003)
Registration: Please register here for the course. You can unregister here. Within a few weeks after the semester starts, you will of course also have to subcribe to the HISPOS system of the university.
Content: Graph algorithms, algorithmic geometry, string algorithms, generic methods, advanced datastructures.
Audience: The course counts as computer science lecture (4 SWS, 9 CP). Prerequisites are the course Fundamentals of Algorithms and Data Structures and the theoretical contents of the lectures "Programming 1" and "Programming 2". This includes basic datastructures, runtime analyses, graphs and trees, BFS and DFS, sorting and hashing. The lecture will be given in English.

Schedule:
Date Lecturer Topic Reference Exercises
12.10.2009 TF, FN, RvS Introduction and Short Exam Solutions
14.10.2009 RvS Maximum Flows Cormen 26.1-2
19.10.2009 RvS Maximum Flows 1, Solutions
21.10.2009 RvS MF, Bipartite matching Cormen 26.3
26.10.2009 RvS Minimum spanning trees: Kruskal, Prim Cormen 23 2, Solutions
28.10.2009 RvS (Fibonacci) heaps Cormen 19
2.11.2009 RvS Linear programming Cormen 29 3, Solutions
4.11.2009 RvS Approximation algorithms Cormen 35
9.11.2009 FN Approximation algorithms (Vertex Cover, Knapsack) Cormen 35, Vazirani 8 4, Solutions
11.11.2009 FN Dynamic Programming (LCS) Randomized Algorithms (MinCut) Cormen 16, paper of Karger and Stein (Chapter 8)
16.11.2009 FN Local Search, Simulated Annealing, Evolutionary Algorithms Michiels 2, 4, Neumann 3 5, Solutions
18.11.2009 FN Markov, Chernoff, Coupon Collectors, Runtime of EAs Motwani 3,4, paper of Droste et al, Neumann 5
23.11.2009 FN Runtime EAs, Minimum Spanning Trees, Shortest Paths Neumann 7, paper of Doerr et al 6, Solutions
25.11.2009 FN Tabu Search, Branch and Bound
30.11.2009 FN String Matching Part I Cormen 34
02.12.2009 FN String Matching Part II Cormen 34
07.12.2009 FN Suffix Trees Heun, Nelson 7, Solutions
09.12.2009 TF, FN, RvS Midterm Exam Solutions
14.12.2009 TF Convex Hull Cormen 35 8, Solutions
16.12.2009 TF Line Segment Intersection, Voronoi Diagrams Cormen 35, FU Hagen Script
04.01.2010 TF Voronoi Diagrams de Berg 9, Solutions
06.01.2010 TF Delaunay Triangulation, Volume Computation de Berg
11.01.2010 TF Approximation Algorithms Karp et al. 10, Solutions
13.01.2010 TF Volume Approximation Algorithms Karp et al.
18.01.2010 RvS Online algorithms 11, Solutions
20.01.2010 RvS Randomized algorithms
25.01.2010 FN Ordered Binary Decision Diagrams Wegener 3.1, 3.3, Sieling 3, 6 12
27.01.2010 TF Fixed-parameter Algorithms Niedermeier
01.02.2010 TF Kernelization, Master-Theorem Niedermeier, Cormen et al.
03.02.2010 TF last lecture none
08.02.2010 TF, FN, RvS Final Exam Solution
07.04.2010 TF, FN, RvS Re-Exam

Exercises:
Day Time Tutor Room
Tuesday 14-16 Tomasz Jurkiewicz (only English) Room SR 0.15, Building E1.3 (Computer Science)
Thursday 14-16 Karl Bringmann (English or German) Room SR I, Building E2.5 (Mathematics)
Thursday 16-18 Ali Pourmiri (only English) Room 0.23, Building E1.4 (MPII)
Friday 14-16 Stefan Schuh (English or German) Room 0.24, Building E1.4 (MPII) (on 18.12. in 0.23)

Midterm Exam: 09.12.2009, 12-14 in the big Hörsaal of the new building E2.2., admission details
Final Exam: 08.02.2010, 12-14 in the big Hörsaal of the new building E2.2.
Re-Exam: 07.04.2010, 15-17 in the big Hörsaal of the new building E2.2.
Grades: The final grades (including the re-exam) can be found here. Everybody who passed can pick up their "Schein" from our secretaries' office (room 302, building E1.4).
Credit: To get admitted to the midterm exam, one has to get 50% of the points in the exercises till the midterm. To get admitted to the final exam, one has to get 50% of the points in the exercises after the midterm. You also have to show up regularly in the exercise sessions (at most two misses overall).
Your final grade depends on the points scored in both the midterm and the final exam. Each exam will contribute roughly 50% to the final result. A grade of four or better will be required to pass.
There will also be a make-up exam. Anyone who got admitted to the final exam will be allowed to participate in the re-exam (that is, including those who passed). Your grade in the re-exam will replace both, the midterm and the final grade, but only if it is better; otherwise, the previous grade stands.
Entry check: In the first lecture, we have a short written exam to check to what extent you know the basics needed for the course. It is strongly recommended to attend, but the grade does not count for the final grade. It is still important since all of us (you included) want to know your knowledge about the topics covered.
References: An online version of Graph Theory by R. Diestel can be found on his website.
Cormen: Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms
Heun: V. Heun, Vorlesungsskript: Algorithmen auf Sequenzen
Atallah: M. Atallah, Algorithms and Theory of Computation Handbook
Bender: Online Publication
Nelson: Fast String Searching With Suffix Trees
Neumann: Combinatorial optimization and the analysis of randomized search heuristics
Michiels, Aarts, Korst: Theoretical aspects of local search
Motwani, Raghavan: Randomized Algorithms
Gaertner: Algorithmische Geometrie
de Berg, Cheong, van Kreveld, Overmars: Computational geometry
Detlef Sieling: Binary Decision Diagrams
Vijay V. Vazirani: Approximation Algorithms, Springer
Future courses: see www.mpi-inf.mpg.de/departments/d1/teaching.html.