Data Structures and Algorithms
Winter 01/02

Exams

• Final results
• example solutions for midterm

Course Notes and Slides

• October 23-30: Basic graph algorithms are mostly taken from Mehlhorn, vol 2, chapter 4. You might also want to look at a short intro from Info V. Here is a compact writeup of the algorithm for solving 2SAT problems using SCC computations.
• October 30: Shortest paths: Some basic stuff from InfoV. Section 4.7 in Kurt Mehlhorns book. Excerpts from slides by Kurt Mehlhorn from last years course.
• November 6:Radix heaps.
• November 8: Priority queues operations in time O(log log C) using van Emde Boas trees (a similar version appeared in Information Processing Letters, volume 35, pages 183-189, 1990.) Here is an even shorter write up with some code fragments.
• November 13: Guest lecture by Ulrich Meyer on shortest paths in linear average time. The lecture covers Sections 1-3.3.
• November 15-27: Maximum Flows. Slides by Kurt Mehlhorn.. The basic concepts and algorithms can be found in Sections 4.9.1 and 4.9.2 of Kurt Mehlhorn's book. Our treatment of the preflow-push algorithm follows Cheriyan and Mehlhorn, IPL, 69:239-242, 1999 respectively the LEDA book. Other good descriptions are in [Cormen Leiserson Rivest] and [Ahuha, Magnanti Orlin]. The treatment Here is a very short summary of results on Dinitz algorithm as presented in the lecture. Slides and the corresponding paper on the binary blocking flow algorithm.
• November 27-Christmas, Basic Optimization. Slides. Slides on Constraints from a talk by Kurt Mehlhorn.
• January 8-10: Exact string matching. Knuth-Morris-Pratt and Boyer-Moore algorithms. For the interested, but outside this course, there is a large collection of exact string matching algorithms with animations.
• January 15-22: Suffix trees. Write up in two parts: first part and second part, or in one piece.
• January 24-29: Approximate string matching.
• January 31-February 14: Geometry. Slides for convex hulls, Delaunay triangulations, and Voronoi diagrams. An application of Delaunay triangulations: Energy optimal paths in radio networks (Section 2 is covered in the lecture). A short write up on Line segment intersection. Program fragments for line segment intersection.
• February 14-February 21: Hashing. Some material on hashing with chaining and hashing with linear probing and Code. Material for Cuckoo Hashing, a minimalistic implementation, and the LEDA implementation. The original stuff can be found on Rasmus Pagh's home page (slides, code, and paper).

Exercises