Data Structures and Algorithms
Winter 03/04

Slides and Course Notes

• October 20,22: Introduction, graph notation, and graph representation (updated Oct. 24).
• October 27,29: Graph traversal (BFS, DFS) (updated Nov. 3). BFS is explained in a similar way in most textbooks. The strongly connected component algorithm in Kurt Mehlhorn's book is very similar to our presentation.
• October 29-Nov 5: Shortest Paths (updated Nov. 13) (1up .ps). The van Emde Boas data structure is described in this paper by Mehlhorn and Näher. The tuned implementation is described here. Another description giving a priority queue priority queue.
• November 10: Basic 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. The smallest examples of graphs where the Ford-Fulkerson algorithm may not terminate.
• November 12: Dinitz algorithm. slides for maximum flow (replaces Kurt Mehlhorn's slides except for the "basic stuff" up to Ford Fulkerson) (1up .ps). The paper and slides (1up .ps) on optimal multicasting.
• November 17,19: Max. Flow using Preflow Push. 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].
• November 24: String matching. Slides (1up .ps). More details by Juha Kärkkäinen.
• November 26: String sorting. Slides for string and suffix sorting (1up .ps). More details by Juha Kärkkäinen.
• December 1: Suffix sorting. A paper describing the algortihm. Some more slides: finding lcps and constructing suffix trees (1up .ps).
• December 3: Hashing (1up .ps).
• December 8: Minimum Spanning Trees (1up .ps).
• January 5: Planar Convex Hull, definitions, slow convex hull algorithm, Graham's scan, Jarvis's march, Chan's algorithm. (from Chapter 1, "Computational Geometry" by Mark de Berg et al. Chan's algorithm can be found in "Optimal output-sensitive convex hull algorithms in two and three dimensions", Discrete and Computational Geometry, 16, 1996, 361-368.) Notes
• January 7: Line Segment Intersection, Convex Polygon Intersection (from Chapter 8, "Data structures and Algorithms" by Kurt Mehlhorn.) Notes
• January 12: Half-plane intersection, Linear Programming in 2 dimensions: deterministic incremental algorithm and randomized algorithm (from Chapter 4, Computational Geometry by Mark de Berg et al.) Notes
• January 14: Randomized incremental algorithm for 2 dimensional linear programming (contd. from last lecture), Randomized incremental algorithm for smallest enclosing disc, Introduction to point-line duality. ( from Chapter 4, Computational Geometry by Mark de Berg et al.) Notes
• January 19: Voronoi Diagrams: definitions, properties, Fortune's algorithm (from Chapter 7, Computational Geometry by Mark de Berg et al.) Notes
• January 21: Fortune's algorithm (contd.), Doubly connected edge lists, Delaunay triangulation: definition, properties. (from Chapters 2, 7, and 9 Computational Geometry by Mark de Berg et al.) Notes
• January 26: Randomized incremental algorithm for Delaunay triangulation, relation between Delaunay triangulation and 3-D lower convex hull. (from Chapter 9, Computational Geometry by Mark de Berg et al.) Notes
• January 28: Planar point location: Randomized incremental algorithm (from Chapter 6, Computational Geometry by Mark de Berg et al.) Notes
• February 2-9,16-18: Optimization (1up .ps) The old lecture notes are mostly superseded by the manuscript, except for the Section on greedy algorithms.
• February 11: Guest lecture by Rene Beier: The Knapsack Problem. slides: ps pdf, papers: 1 2

Exercises