References for Part Four

   

The primary references for this section are the books by Knuth; Baeza-Yates and Gonnet; Mehlhorn; and Cormen, Leiserson, and Rivest. Many of the algorithms covered here are treated in great detail in these books, with mathematical analyses and suggestions for practical applications. Classical methods are covered thoroughly in Knuth; the more recent methods are described in the other books, with further references to the literature. These four sources, and the Sedgewick-Flajolet book, describe nearly all the "beyond the scope of this book" material referred to in this section.

The material in Chapter 13 comes from the 1996 paper by Roura and Martinez, the 1985 paper by Sleator and Tarjan, and the 1978 paper by Guibas and Sedgewick. As suggested by the dates of these papers, balanced trees are the subject of ongoing research. The books cited above have detailed proofs of properties of red black trees and similar structures and references to more recent work.

The treatment of tries in Chapter 15 is classical (though complete implementations are rarely found in the literature). The material on TSTs comes from the 1997 paper by Bentley and Sedgewick.

The 1972 paper by Bayer and McCreight introduced B trees, and the extendible hashing algorithm presented in Chapter 16 comes from the 1979 paper by Fagin, Nievergelt, Pippenger, and Strong. Analytic results on extendible hashing were derived by Flajolet in 1983. These papers are must reading for anyone wishing further information on external searching methods. Practical applications of these methods arise within the context of database systems. An introduction to this field is given, for example, in the book by Date.

R. Baeza-Yates and G. H. Gonnet, Handbook of Algorithms and Data Structures, second edition, Addison-Wesley, Reading, MA, 1984.

R. Bayer and E. M. McCreight, "Organization and maintenance of large ordered indexes," Acta Informatica 1, 1972.

J. L. Bentley and R. Sedgewick, "Sorting and searching strings," Eighth Symposium on Discrete Algorithms, New Orleans, January, 1997.

T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, second edition, MIT Press/McGraw-Hill, Cambridge, MA, 2002.

C. J. Date, An Introduction to Database Systems, seventh edition, Addison-Wesley, Boston, MA, 2002.

R. Fagin, J. Nievergelt, N. Pippenger and H. R. Strong, "Extendible hashing a fast access method for dynamic files," ACM Transactions on Database Systems 4, 1979.

P. Flajolet, "On the performance analysis of extendible hashing and trie search," Acta Informatica 20, 1983.

L. Guibas and R. Sedgewick, "A dichromatic framework for balanced trees," in 19th Annual Symposium on Foundations of Computer Science, IEEE, 1978. Also in A Decade of Progress 1970 1980, Xerox PARC, Palo Alto, CA.

D. E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching, second edition, Addison-Wesley, Reading, MA, 1997.

K. Mehlhorn, Data Structures and Algorithms 1: Sorting and Searching, Springer-Verlag, Berlin, 1984.

S. Roura and C. Martinez, "Randomization of search trees by subtree size," Fourth European Symposium on Algorithms, Barcelona, September, 1996.

R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996.

D. Sleator and R. E. Tarjan, "Self-adjusting binary search trees," Journal of the ACM 32, 1985.


   
Top


Algorithms in Java, Part 1-4
Algorithms in Java, Parts 1-4 (3rd Edition) (Pts.1-4)
ISBN: 0201361205
EAN: 2147483647
Year: 2002
Pages: 158

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net