max planck institut
mpii logo Minerva of the Max Planck Society

Benjamin Doerr: Teaching

Algorithms and Datastructures (winter 07/08)

PD Dr. Benjamin Doerr and Dr. Ernst Althaus

Important Announcements: Scheine (Grades) can be picked up from our secretaries office.
If you want to see your repetition exam, please make an appointment with Ernst Althaus by email.

Time: Monday + Wednesday 14-16. Start: October 24, 2007. Exercises see Exercises page.
Room: Monday: Room 001, Building E1.3, Wednesday: Room 002, Building E1.3
Registration: Please subscribe electronically until Wednesday, October 24, at 16.00.
Exercises: The Exercises can be found here.
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 theoretical contents of the lectures "Programming 1" and "Programming 2" as taught 2005-2006 (not the current module description!). This includes basic datastructures, runtime analyses, graphs and trees, BFS and DFS, sorting and hashing. The lecture will be given in English.

Forum: For the online forum we use the CLIX electronic teaching system of the university. You can login with your regular university students account (usually "s9xxyyyy" where "xx" are the first two letters of your first name and "yyyy" the first four letters of your last name).

In the CLIX system you will find the course Algorithms and Data Structures (note that you have to set the course language to German to find it with the build-in search). You can access it after adding it to your shopping cart.

The section communication contains an announcement board, a forum, and a repository for documents.
In future, important announcements like changes in the time/place of a lecture or exercise group will be made in this section. Check it regularly to stay up to date.
In the forum you can discuss anything concerning the lecture and exercises as well as asking questions to the lecturers and tutors.
Lecture details:
Date Lecturer Topic Reference
Oct 24 EA+BD Short written evaluation of prerequisites
Oct 29 BD O-Notation, Graphs, graph representations, simple graph exploration Lecture, links. Graphs: not 1.4.3, 1.5.4 to 1.5end; 1.3 only the definitions.
Oct 31 BD Graph search (distances, tree, BFS, shortest path tree) Lecture
Nov 5 Kurt Mehlhorn RingVL: Schnelle Multiplikation ganzer Zahlen Notes: HS002, in German
Nov 7 BD BFS to compute/estimate rad and diam, DFS Lecture, slides
Nov 12 BD DFS: Parenthesis thm., white path thm. classification of edges Lecture
Nov 14 BD Topological sorting, strongly connected components Lecture, slides
Nov 19 BD Minimum spanning trees, cut property Lecture, slides
Nov 21 BD Prim, Kruskal, heaps Lecture, slides, MST, union-find data structure
Nov 26 BD Matroids and greedy algorithms, shortest paths Lecture, slides
Nov 28 BD Shortest paths (dags, Bellman-Ford, Dijkstra) Lecture, slides, xkcd
Dec 3 DJ+SC Chefbremsers answer questions concerning mid-term exam
Dec 5 EA Closest Pairs Gaertner, de Berg
Dec 10 Midterm Exam 14:00 - 18:00, Building E2.5 (Mathematics), Room I
Dec 12 EA Definitions: Voronoi-Diagram, Delaunay-Triangulation, Planar Graph Gaertner, de Berg
Dec 17 EA Relation Voronoi-Diagram and Delaunay-Triangulation
Dec 19 EA Randomized Incremental Construction for Delaunay-Triangulations
[christmas holidays]
Jan 7 EA Range search
Jan 9 EA Range Search Gaertner, de Berg
Jan 14 EA Pattern Matching Cormen
Jan 16 EA Pattern Matching
Jan 21 EA Suffix Trees Heun, Atallah, Nelson
Jan 23 SC Huffman Encoding
Jan 28 EA Suffix Trees, Lowest Common Ancestors Heun, Bender
Jan 30 EA Lowest Common Ancestors
Feb 4 -- Rosenmontag (no lecture)
Feb 6 DJ+BD Q&A final exam, randomized algorithms
Feb 11 all Final exam 14:00 - 18:00, Building E2.5 (Mathematics), Room I
Feb 13 BD Randomized algorithms Voluntary global exercise class, 16-18, R.024 MPI
Feb 18 SC Solution to final exam 16:15-?? Inspection of exams (MPI ground floor), informal nothing (AC)
Feb 20 BD+EA Topics for bachelor and master theses

Exams/Credit: There is a midterm exam on December 10, 2007, and a final exam on February 11, 2008. To get admitted to the midterm and the final exam, one has to get sufficiently many points in the exercises and show up regularly in the exercise sessions (at most two misses). Eventually, there will also be a repetition examination.

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. You get a "Schein", if you reach a grade of "four" or better.

Anyone who got admitted to the final exam will be allowed to participate in the repetition exam. Irrespective of whether they passed or failed in the final. Grades in the repetition exam can only improve the total performance. If better, they will replace the combined grades from midterm and final. (In particular, if you scored very high in the midterm but failed in the final, a successful repetition exam will determine the grade for the whole course. The grade from the midterm will get overridden in this case.) The repetition exam will be oral or written, depending on the number of candidates.

Entry prerequisites check: In the first lecture on October 24, 2007, we have a short written exam to check to what extent you know the basics needed for the course. You have to attend. The grade does not count for anything. We do this check because we want to know your knowledge, and because we want you to know your knowledge. The exam only covers things you really should know, so no preparation is necessary.

Midterm Exam: The midterm is on December 10, 2007. It takes three (3) hours somewhere in the 14-18h interval. To be admitted, you need 50% of the points from the exercises up to the series you have to submit untill December 3.

You may use one (1) single-sided hand-written page (size DIN A4) of arbitrary notes. [Note: In the final exam, you may use one hand-written sheet (both sides).] No other books, notes, electronic devices etc. are allowed. You may bring reasonable food etc. if you plan to use plenty of time. You may use your own paper, which of course should not contains any other notes. If I catch you cheating, (a) you fail and face all other problems the "Studienordnung" tells you, and (b) I hate you for that. So better don't do that.

Final Exam: The final exam is on February 11, 2007. It takes three (3) hours somewhere in the 14-18h interval. To be admitted, you need 50% of the points from the exercises series that are returned later than December 5.

If you did not have 50% of the points from the exercises series you had to submit untill December 3 but were still allowed to take the midterm, you will be required to have 50% of the points from all exercises series to be admitted to the final exam.

You may use one (1) double-sided hand-written page (size DIN A4) of arbitrary notes. No other books, notes, electronic devices etc. are allowed. You may bring reasonable food etc. You may use your own paper, which of course should not contain any other notes.

Re-Exam: The re-exam takes place Thursday, 10th of April, 14:00-18:00 in room 021 of the MPI. It will be a written exam. You have to register for the re-exam until March 14. To do so, hand in (to any of the chefbremsers) a handwritten and signed piece of paper saying that you wish to participate, and that you understood the consequences. It should also contain your name and email address.

The consequences are simple: If you don't show up, you fail the course (not just the re-exam). If you participate, the better grade of (a) the re-exam and (b) the grade determined by mid-term and final exam will be the resulting grade. The re-exam covers the whole lecture including elementary stuff on randomized algorithms (but not the tenure games discussed in the exercise).

Literature: 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

Gaertner: Algorithmische Geometrie

de Berg: de Berg, van Kreveld, Overmars, Schwarzkopf, Computational geometry