Handouts

1) Balanced Binary Search Trees

• Slides:
  • Balanced Binary Search Trees

• Other Material:
  • Binary Search Trees
  • CLRS Chapter 12 - Binary Search Tree
  • Binary Search Tree Visualization (recommended)
  • Binary Search Trees (B. Hasti - University of Wisconsin-Madison)
  • AVL Trees
  • AVL Trees (R. Pattis - University of California)
  • AVL Tree Visualization (recommended)
  • AVL Trees (E. Alexander - University of Wisconsin-Madison)
  • Red-Black Trees
    • CLRS Chapter 13 - Red-Black Trees
    • Red-Black Tree Visualization (recommended)
    • Red-Black Trees (B. Hasti - University of Wisconsin-Madison)
    • An Introduction to Binary Search and Red-Black Trees (TopCoder)
    • A Practical view on Red-Black Trees (Eternally Confuzzled)
    • Left-leaning Red-Black Trees [slides] (R. Sedgewick)

2) Self Adjusting Data Structures

• Slides:
  • Self Adjusting Data Structures

• Other Material:
  • Amortized Analysis
    • Amortized Analysis (my own slides, from 18/19 Algorithms course)
  • Self Organizing Lists
    • Amortized Analysis of Move-to-Front (MTF) List Rearrangement with paid exchanges (MIT)
    • On line algorithms: list update and paging (A. Blum - Carnegie Mellon University)
  • 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

• Lecture Notes:
  • Probabilistic Data Structures (selected lecture notes from J. Erickson - University of Illinois)

• Other Material:
  • Probabilistic Analysis
    • Probabilistic Analysis and Randomized Algorithms (my own slides, from 18/19 Algorithms course)
  • 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
    • Skip Lists (slides from C. Kingsford - CMU)
    • Skip Lists Visualization (Y. Lucet - University of British Columbia)
    • Skip Lists (Goodrich and Tamassia - DSA Book)
    • Wikipedia entry on Skip Lists
    • Pugh, W. (1990). Skip lists: a probabilistic alternative to balanced trees. Communications of the ACM, 33(6), 668-676.
  • 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

• Slides:
  • Quadtrees (selected slides from C. Kingsford - University of Marlyand)
  • 2D Range Search (kd-trees and 2D range trees) (selected slides from C. Kingsford - University of Marlyand)

• Other Material:
  (Note: most of the visualizations are java applets (you meed need an old browser or a tool like appletviewer)
  • Quadtrees
    • PR Quadtree Demo (Brabet & Samet - University of Maryland)
    • PR Bucket Quadtree Demo (Brabet & Samet - University of Maryland)
    • MX Quadtree Demo (Brabet & Samet - University of Maryland)
    • Point Quadtree Demo (Brabet & Samet - University of Maryland)
    • Spatial Index Demos (Brabet & Samet - University of Maryland)
    • MX Quadtree Visualization (Ivan Kuckir)
  • 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)

• Slides:
  • The LCA Problem Revisited (adapted slides from M. Bender and M. Farach-Colton)

• Other Material:
  • Range Minimum Query and Lowest Common Ancestor (Topcoder tutorial by danielp)
  • Bender, M. A., & Farach-Colton, M. (2000, April). The LCA problem revisited. In Latin American Symposium on Theoretical Informatics (pp. 88-94). Springer.
  • "The LCA Problem Revisited" talk/slides (Michael A. Bender and Martín Farach-Colton)
  • Fischer, J., & Heun, V. (2006, July). Theoretical and practical improvements on the RMQ-problem, with applications to LCA and LCE. In Annual Symposium on Combinatorial Pattern Matching (pp. 36-48). Springer.

6) (some more) 1D problems

• Lecture Notes:
  • Binary Indexed Trees (topcoder tutorial)
  • RMQ with segment trees (topcoder tutorial)

• Other Material:
  • Fenwick, P. M. (1994). A new data structure for cumulative frequency tables. Software: Practice and Experience, 24(3), 327-336.
  • Various Usages of BITs
  • Segment Tree (Wikipedia)
  • Segment Tree | Set 1 (Sum of given range) (GeeksforGeeks)
  • Segment Tree | Set 2 (Range Minimum Query) (GeeksforGeeks)
  • Segment Trees and Lazy Propagation (My Experience Blog)
  • Lazy propagation in segment tree? (Stackoverflow)

7) String Matching

• Slides:
  • 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 Tree
  • Suffix Array
  • 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

Last Update: