School of Engineering and Applied Science Department of Computer Science CSci 133 -- Algorithms and Data Structures I http://www.seas.gwu.edu/~csci133/spring05 Prof. Michael B. Feldman mfeldman@gwu.edu

A Brief Bibliography of Important Original Works on Algorithms and Data Structures

In this short bibliography I have tried to select the most important original articles in classical data structures and algorithms. These are (mostly) the real primary sources, the articles that introduced the famous -- and still very widely-used -- algorithms and technques we all study in college now. The ACM publications -- even the very old ones -- are now all online in the ACM Digital Library.

Adelson-Velskii, G. M., and E. M. Landis [1962]: “An Algorithm for the Organization of Information,” Dokl. Akad. Nauk SSSR, Mathemat., 146:2, pp. 263-266. Introduces AVL trees.

Cardelli, L., and P. Wegner [1985]: “On Understanding Types, Data Abstraction, and Polymorphism,” ACM Computing Surveys, 17:4, pp. 471-522. An important early survey on object-oriented programming.

Guttag, J. V., E. Horowitz, and D. R. Musser [1978]: “Abstract Data Types and Software Validation,” Communications of the ACM, 21:12, pp. 1048-1064. One of the early papers on ADTs.

Hoare, C. A. R. [1962]: “Quicksort,” Computer Journal,  5:1, pp. 10-15.

Knuth, D.E. [1973]: Fundamental Algorithms, 2d ed. Addison-Wesley, Reading, Massachusetts. ISBN 0-201-03809-9.

Knuth, D.E. [1973]: Sorting and Searching.  Addison-Wesley, Reading, Massachusetts. (ISBN 0-201-03803-X) The best collection of sorting and searching algorithms ever published. Thirty years old and still timely.

Liskov, B. H., and S. N. Zilles [1975]: “Specification Techniques for Data Abstractions,” IEEE Transactions on Software Engineering,  SE-1:1, pp. 7-18. Another early ADT paper, in the first issue of this journal.

Liskov, B. H., and S. N. Zilles [1977]: “Abstraction Mechanisms in CLU,” Communications of the ACM,  20:8, pp. 564-576. Specification vs. implementation.

Lukasiewicz, J. [1951]: Aristotle's Syllogistic from the Standpoint of  Modern Formal Logic. Clarendon Press, England. Introduces “Polish” notation.

Martin, W. [1971]: “Sorting,” Computing Surveys, 3 (4): 147.

Maurer, W. D. [1968]: “An Improved Hash Code for Scatter Storage,” Communications of the ACM, 11:1. Introduces quadratic hashing. (Yes, it's the same W.D. Maurer who teaches at GW!)

Maurer, W. D., and T. Lewis [1975]: “Hash Table Methods,” Computing Surveys, 7:1, pp. 5-19. Excellent survey article on hash tables, again by GW's own W.D. Maurer.

Nievergelt, J. [1974]: "Binary Search Trees and File Organization," Computing Surveys, 6:3, pp. 195-207.

Perlis, A., and C. Thornton [1960]: “Symbol Manipulation by Threaded Lists,” Communications of the ACM,  3:4, pp. 195-204. Threading binary trees.

Samelson, K., and F.L. Bauer [1960]: “Sequential Formula Translation,” Communications of the ACM, 2:2, pp. 76-83. Translating with a stack.

Shell, D.L. [1959]: “A High-Speed Sorting Procedure,” Communications of the ACM,  2:7, pp. 30-32. Shell sort.

Shell, D.L. [1971]: “Optimizing the Polyphase Sort,” Communications of the ACM,  14:11, pp. 713-719.

Singleton, R.C. [1969]:  “Algorithm 347: an Algorithm for Sorting with Minimal Storage,” Communications of the ACM,  12:3, pp. 185-187. Quicksort.

Stroustrup, B. [1982]: “Classes: an Abstract Data Type Facility for the C Language,” SIGPLAN Notices, 17:1, pp. 354-356. The very first published article on what became C++.

Williams, J. W. J. [1964]: “Algorithm 232 (Heapsort),” Communications of the ACM, 7:6, pp. 347-348.