max planck institut
informatik
informatik
Tobias Friedrich, Frank Neumann, Rob van Stee
| 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: |
| ||||||||||||||||||||
| Exercises: |
| ||||||||||||||||||||
| 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. |