Post-Midterm Topic Outline

1. Searching
   • Sequential Search (British Museum Algorithm)
   • Speedups
     • sorting
     • self-organizing files
   • binary searching
   • binary search trees
   • balanced binary search trees
     • global balance
     • local balance (AVL trees)
       • insertions, rotations, deletions
   • Splay trees
     • Splays, rotations, insertions, deletions
   • list arrays
   • skip lists
   • B Trees
     • insertions, deletions, rotations
     • 2-3 trees, 2-3-4 trees
     • red-black trees
   • B+ Trees
   • Range Trees
   • Tries (Digital searching)
     • Patrician Tries
2. Hashing
   • Hash functions
   • Separate Chaining
   • In place chaining
   • Lampson's method
   • Open Addressing
     • Linear probing
     • quadratic probing
     • double hashing
       • Brent's algorithm
       • Gonnet Munro
       • Optimal
   • Extendible hashing
   • Linear hashing
3. Point Methods
   • Sequential List
   • inverted list
   • Grids
     • Grid method
     • grid file
     • Excell
   • Quad Trees
     • Point Quadtree
     • MX quadtree
     • PR quadtree
     • MX-CIF quadtree
   • K-D trees
     • K-D tree
     • PR K-D tree
     • Adaptive K-D tree
   • Hashing methods
     • bit-interleaving
     • Order Preserving linear hashing
4. Rectangles
   • Range Searches (organize points and search for points in a window)
     • 2-d Range trees
     • Priority Search trees
     • Range Priority Trees
   • Other Operations (organize rectangles)
     • Interval representations
     • R-Trees
5. Other topics
   • comparisons
     • time (speed)
     • space
     • different operations
     • organize space of values or actual data
   • Set Theory
   • Amortized complexity