Bibliography
  1. Corman, Leiserson and Rivest, Introduction to Algorithms, McGraw-Hill.
  2. R. E. Tarjan, Data Structures and Network Algorithms, SIAM Monograph #44 (1983). (Reserved.)
  3. K. Mehlhorn, Data Structure and Algorithms 1: Sorting and Searching, Springer-Verlag, 1984.
  4. B. Chazelle, Lecture Notes.
  5. A. Aho, J. Hopcroft and J. Ullman, The design and analysis of computer algorithms , Addison Wesley. 318-361, (1974), (pattern matching).
  6. J.L. Carter and Mark N. Wegman, Universal classes of hash functions, JCSS, 18, (1979), 143-154.
  7. J. R. Driscoll, D.D.K. Sleator, and R.E. Tarjan, Fully-persistent Lists with Catenation JACM, 41(5), Sept. 1994, 943-959.
  8. Fredman, Kolmos and Szemeredi, Storing a sparse table with O(1) worse case access time, JACM 31 (1984) 538-544.
  9. Culberson, Probabilistic Analysis of Binary Search Trees STOC 85, 205-212.
  10. Fredman and Tarjan, Fibonacci Heaps and their uses in improved network optimization algorithms FOCS (1984), 338-346, JACM 34 (1987), 596-615.
  11. Knuth, Morris and Pratt, Fast pattern matching in strings, SIAM J. Comp., 6, (1977), 323-350.
  12. N. Sarnak and R. Tarjan, Planar point location using persistent search trees, CACM, 29, (1986), 669-679.
  13. J.L. Bentley and J.B. Saxe, Decompositional searching problems I: static to dynamic transformations. J. Algorithms 1 (1980) 301-358.
  14. Eppstein, Galil, Italiano and Nisssenzweig, Sparsification -- A technique for speeding up dynamic graph algorithms
  15. McCreight,
  16. W. Pugh, Skip lists: A probabilistic alternative to balanced trees CACM June, 90, pp. 668-676.
  17. Rajeev Motwani and Prabhakar Raghavan Randomized Algorithms, Cambridge University Press (1995) U.D.C. 519.688 MO.
  18. K. Mulmuley, Computational Geometry: An Introduction through Randomized Algs., Chapter 1. Prentice Hall, 1994.
  19. Eisenbarth, Ziviani, Gonnet, Mehlhorn, D Wood, The theory of fringe analysis and its application to 2-3 trees and B-trees Inf and Control, 55, 125-174, 1082.
  20. Fredman, M. and Dan Willard, BLASTING through the information theoretic barrier with FUSION TREES, STOC 1990, 1-7, also, JCSS 47, (1993), 424--436.

Some useful pointers

  1. Ming Li's course at Waterloo