---

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
• Randomized fractional cascading
• 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

---