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