Handouts
Overview
- Balanced Binary Search Trees (binary search trees, AVL trees, red-black trees)
- Self Adjusting Data Structures (self organizing lists, splay trees)
- Probabilistic Data Structures (randomized trees, treaps, skip lists, bloom filters)
- Spatial Data Structures (quadtrees, kd-trees, 2d range trees)
- Lowest Common Ancestor (LCA) and Range Minimum Query (RMQ) (srqt buckets, sparse tables, +/- 1 case, cartesian trees)
- (some more) 1D problems (fenwick trees, segment trees, lazy propagation)
- String Matching (naive, KMP, Rabin-Karp, Tries, Suffix Trees, Suffix Arrays)
1) Balanced Binary Search Trees
- Other Material:
- Binary Search Trees
- AVL Trees
- Red-Black Trees
2) Self Adjusting Data Structures
- Other Material:
- Amortized Analysis
- Self Organizing Lists
- Splay Trees
- Splay Tree
Visualization (D. Galles - University of San Francisco)
- 1999
Paris Kanellakis Award (given to Sleator and Tarjan for the
Splay Tree data structure)
- Splay Trees Recitation (D. Kozen - Cornell University)
- Sleator, D. D., & Tarjan, R. E. (1985). Self-adjusting binary search trees. Journal of the ACM (JACM), 32(3), 652-686.
- Lee, E. K., & Martel, C. U. (2007). When to use splay trees. Software: Practice and Experience, 37(15), 1559-1575.
3) Probabilistic Data Structures
- Other Material:
- Probabilistic Analysis
- Treaps and Randomized Binary Search Trees
- Red Black Trees, Heaps and Treaps (T. Veldhuizen - University of Waterloo)
- Gnarley trees | visualization of algorithms and data structure
- Wikipedia entry on Treaps
- Aragon, C. R., & Seidel, R. G. (1989, October). Randomized search trees. In Foundations of Computer Science, 1989., 30th Annual Symposium on (pp. 540-545). IEEE.
- Seidel, R., & Aragon, C. R. (1996). Randomized search trees. Algorithmica, 16(4-5), 464-497.
- Martínez, C., & Roura, S. (1998). Randomized binary search trees. Journal of the ACM (JACM), 45(2), 288-323.
- Skip Lists
- Bloom Filters
- Wikipedia entry on Bloom Filters
- Bloom Filters By Example
- Bloom Filters (with visualization) (Jason Davies)
- Some possible hash functions: murmur | FNV | Jenkins
- Broder, A., & Mitzenmacher, M. (2004). Network applications of bloom filters: A survey. Internet mathematics, 1(4), 485-509.
- Kirsch, A., & Mitzenmacher, M. (2008). Less hashing, same performance: Building a better Bloom filter. Random Structures & Algorithms, 33(2), 187-218.
4) Spatial Data Structures
- Other Material:
(Note: most of the visualizations are java applets (you meed need an old browser or a tool like appletviewer)
- Quadtrees
- KD-Trees and 2d Range Trees
- kd-tree Demo (Brabet & Samet - University of Maryland)
- 2D range tree Demo (Brabet & Samet - University of Maryland)
- Spatial Index Demos (Brabet & Samet - University of Maryland)
- KD Trees (adapted from M. Kreveld, one of the authors of "
Computational Geometry: Algorithms and Applications." book)
- Range Trees (adaptef from M. Kreveld, one of the authors of "
Computational Geometry: Algorithms and Applications." book)
- Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9), 509-517.
- Chazelle, B., & Guibas, L. J. (1986). Fractional cascading: I. A data structuring technique. Algorithmica, 1(1-4), 133-162.
- Chazelle, B., & Guibas, L. J. (1986). Fractional cascading: II. applications. Algorithmica, 1(1-4), 163-191.
5) Lowest Common Ancestor (LCA) and Range Minimum Query (RMQ)
6) (some more) 1D problems
7) String Matching
- Other Material:
- Substring Search (Princeton University)
- Exact String Matching Algorithms (Christian Charras, Thierry Lecroq, Université de Rouen)
- Visualizing String Matching Algorithms (justinj)
- Visualgo (Steven Halim, National University of Singapore)
- Suffix arrays – a programming contest approach (A. Vladu and C. Negruseri)
- Implementation of Suffix Arrays (CP-Algorithms)
- "Fast pattern matching in strings", DE Knuth, JH Morris, Jr, VR Pratt - SIAM Journal on Computing, 1977
- "Suffix arrays: a new method for on-line string searches", U Manber, G Myers - SIAM Journal on Computing, 1993