Course notes that I have used in my classes:

- A probabilistic construction of a dense bipartite graph with high girth
- Shortcutting lists
- Computing the convex hull of a planar point set
- Planar graphs, Euler's formula, crossing numbers, point-line incidences, and unit-distances
- The closest pair problem: a plane sweep algorithm
- The k-set problem
- Point location in planar subdivisions
- Computing intersections in a set of horizontal and vertical line segments
- Computing intersections in a set of line segments: the Bentley-Ottmann algorithm
- Voronoi diagrams
- Lower envelopes and Davenport-Schinzel sequences
- Finding the majority
- Computing the diameter of a point set: sequential and parallel algorithms
- Solving geometric optimization problems using parametric search
- Solving geometric optimization problems: a randomized approach
- The closest pair problem: a randomized incremental algorithm
- Range trees and the post-office problem
- Amortized analysis
- Skip lists, a randomized dictionary
- Linear Programming, the Ellipsoid Algorithm
- Lower bounds
- Implementing dictionaries using hashing
- Here
are old lecture notes for the course "Selected Topics in
Data Structures", taught in the wintersemester 1993/94 in
Saarbrücken. The following topics are covered:
- Skip lists. But: the skip list notes above are much better.
- The union-find problem
- Range trees and the post-office problem
- Maintaining order in a list