Alfred V. Aho - Data Structures and Algorithms

Data Structures and Algorithms: Bibliography Gotlieb, C. C., and L. R. Gotlieb [1978]. Data Types and Data Structures, Prentice- Hall, Englewood Cliffs, N. J. Greene, D. H., and D. E. Knuth [1983]. Mathematics for the Analysis of Algorithms, Birkhauser, Boston, Mass. Gudes, E., and S. Tsur [1980]. \"Experiments with B-tree reorganization,\" ACM SIGMOD Symposium on Management of Data, pp. 200-206. Hall, M. [1948]. \"Distinct representatives of subsets,\" Bull. AMS 54, pp. 922-926. Harary, F. [1969]. Graph Theory, Addison-Wesley, Reading, Mass. Hirschberg, D. S. [1973]. \"A class of dynamic memory allocation algorithms,\" Comm. ACM 16:10, pp. 615-618. Hoare, C. A. R. [1962]. \"Quicksort,\" Computer J. 5:1, pp. 10-15. Hoare, C. A. R., O.-J. Dahl, and E. W. Dijkstra [1972]. Structured Programming, Academic Press, N. Y. Hopcroft, J. E., and R. M. Karp [1973]. \"An n5/2 algorithm for maximum matchings in bipartite graphs,\" SIAM J. Computing 2:4, pp. 225-231. Hopcroft, J. E., and R. E. Tarjan [1973]. \"Efficient algorithms for graph manipulation,\" Comm. ACM 16:6, pp. 372-378. Hopcroft, J. E., and J. D. Ullman [1973]. \"Set merging algorithms,\" SIAM J. Computing 2:4, pp. 294-303. Huffman, D. A. [1952]. \"A method for the construction of minimum-redundancy codes,\" Proc. IRE 40, pp. 1098-1101. Hunt, J. W., and T. G. Szymanski [1977]. \"A fast algorithm for computing longest common subsequences,\" Comm. ACM 20:5, pp. 350-353. Iverson, K. [1962]. A Programming Language, John Wiley and Sons, New York. Johnson, D. B. [1975]. \"Priority queues with update and finding minimum spanning trees,\" Inf. Processing Letters 4:3, pp. 53-57. http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1213.htm (4 of 9) [1.7.2001 19:33:58]

Data Structures and Algorithms: Bibliography Johnson, D. B. [1977]. \"Efficient algorithms for shortest paths is sparse networks,\" J. ACM 24:1, pp. 1-13. Karatsuba, A., and Y. Ofman [1962]. \"Multiplication of multidigit numbers on automata,\" Dokl. Akad. Nauk SSSR 145, pp. 293-294. Kernighan, B. W., and P. J. Plauger [1974]. The Elements of Programming Style, McGraw-Hill, N. Y. Kernighan, B. W., and P. J. Plauger [1981]. Software Tools in Pascal, Addison- Wesley, Reading, Mass. Knowlton, K. C. [1965]. \"A fast storage allocator,\" Comm. ACM 8:10, pp. 623-625. Knuth, D. E. [1968]. The Art of Computer Programming Vol. I: Fundamental Algorithms, Addison-Wesley, Reading, Mass. Knuth, D. E. [1971]. \"Optimum binary search trees,\" Acta Informatica 1:1, pp. 14- 25. Knuth, D. E. [1973]. The Art of Computer Programming Vol. III: Sorting and Searching, Addison-Wesley, Reading, Mass. Knuth, D. E. [1981]. TEX and Metafont, New Directions in Typesetting, Digital Press, Bedford, Mass. Kruskal, J. B. Jr. [1956]. \"On the shortest spanning subtree of a graph and the traveling salesman problem,\" Proc. AMS 7:1, pp. 48-50. Lin, S., and B. W. Kernighan [1973]. \"A heuristic algorithm for the traveling salesman problem,\" Operations Research 21, pp. 498-516. Liskov, B., A. Snyder, R. Atkinson, and C. Scaffert [1977]. \"Abstraction mechanisms in CLU,\" Comm. ACM 20:8, pp. 564-576. Liu, C. L. [1968]. Introduction to Combinatorial Mathematics, McGraw-Hill, N. Y. Lueker, G. S. [1980]. \"Some techniques for solving recurrences,\" Computing Surveys, 12:4, pp. 419-436. http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1213.htm (5 of 9) [1.7.2001 19:33:58]

Data Structures and Algorithms: Bibliography Lum, V., and H. Ling [1970]. \"Multi-attribute retrieval with combined indices,\" Comm. ACM 13:11, pp. 660-665. Maurer, W. D., and T. G. Lewis [1975]. \"Hash table methods,\" Computing Surveys 7:1, pp. 5-20. McCarthy, J. et al. [1965]. LISP 1.5 Programmers Manual, MIT Press, Cambridge, Mass. Micali, S., and V. V. Vazirani [1980]. \"An algorithm for finding maximum matching in general graphs,\" Proc. IEEE Twenty-first Annual Symp. on Foundations of Computer Science, pp. 17-27. Moenck, R., and A. B. Borodin [1972]. \"Fast modular transforms via division,\" Proc. IEEE Thirteenth Annual Symp. on Switching and Automata Theory, pp. 90-96. Morris, F. L. [1978]. \"A time- and space-efficient garbage compaction algorithm,\" Comm. ACM 21:8, pp. 662-665. Morris, R. [1968]. \"Scatter storage techniques,\" Comm. ACM 11:1, pp. 35-44. Moyles, D. M., and G. L. Thompson [1969]. \"Finding a minimum equivalent graph of a digraph,\" J. ACM 16:3, pp. 455-460. Nicholls, J. E. [1975]. The Structure and Design of Programming Languages, Addison-Wesley, Reading, Mass. Nievergelt, J. [1974]. \"Binary search trees and file organization,\" Computer Surveys 6:3, pp. 195-207. Papadimitriou, C. H., and K. Steiglitz [1982]. Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Englewood Cliffs, N. J. Parker, D. S. Jr. [1980]. \"Conditions for optimality of the Huffman algorithm,\" SIAM J. Computing 9:3, pp. 470-489. Perl, Y., A. Itai, and H. Avni [1978]. \"Interpolation search -- a log log n search,\" Comm. ACM 21:7, pp. 550-553. Peterson, W. W. [1957]. \"Addressing for random access storage,\" IBM J. Res. and Devel. 1:2, pp. 130-146. http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1213.htm (6 of 9) [1.7.2001 19:33:58]

Data Structures and Algorithms: Bibliography Pratt, T. W. [1975]. Programming Languages: Design and Implementation, Prentice- Hall, Englewood Cliffs, N. J. Pratt, V. R. [1979]. Shellsort and Sorting Networks, Garland, New York. Prim, R. C. [1957]. \"Shortest connection networks and some generalizations,\" Bell System Technical J. 36, pp. 1389-1401. Reingold, E. M. [1972]. \"On the optimality of some set algorithms,\" J. ACM 19:4, pp. 649-659. Robson, J. M. [1971]. \"An estimate of the store size necessary for dynamic storage allocation,\" J. ACM 18:3, pp. 416-423. Robson, J. M. [1974]. \"Bounds for some functions concerning dynamic storage allocation,\" J. ACM 21:3, pp. 491-499. Robson, J. M. [1977]. \"A bounded storage algorithm for copying cyclic structures,\" Comm. ACM 20:6, pp. 431-433. Sahni, S. [1974]. \"Computationally related problems,\" SIAM J. Computing 3:3, pp. 262-279. Sammet, J. E. [1968]. Programming Languages: History and Fundamentals, Prentice-Hall, Englewood Cliffs, N. J. Schkolnick, M. [1975]. \"The optimal selection of secondary indices for files,\" Information Systems 1, pp. 141-146. Schoenhage, A., and V. Strassen [1971]. \"Schnelle multiplikation grosser zahlen,\" Computing 7, pp. 281-292. Schorr, H., and W. M. Waite [1967]. \"An efficient machine-independent procedure for garbage collection in various list structures,\" Comm. ACM 10:8, pp. 501-506. Schwartz, J. T. [1973]. On Programming: An Interrum Report on the SETL Project, Courant Inst., New York. Sharir, M. [1981]. \"A strong-connectivity algorithm and its application in data flow analysis,\" Computers and Mathematics with Applications 7:1, pp. 67-72. http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1213.htm (7 of 9) [1.7.2001 19:33:58]

Data Structures and Algorithms: Bibliography Shaw, M., W. A. Wulf, and R. L. London [1977]. \"Abstraction and verification in ALPHARD: defining and specifying iteration and generators,\" Comm. ACM 20:8, pp. 553-563. Shell, D. L. [1959]. \"A high-speed sorting procedure,\" Comm. ACM 2:7, pp. 30-32. Shell, D. L. [1971]. \"Optimizing the polyphase sort,\" Comm. ACM 14:11, pp. 713- 719. Singleton, R. C. [1969]. \"Algorithm 347: an algorithm for sorting with minimal storage,\" Comm. ACM 12:3, pp. 185-187. Strassen, V. [1969]. \"Gaussian elimination is not optimal,\" Numerische Mathematik 13, pp. 354-356. Stroustrup, B. [1982]. \"Classes: an abstract data type facility for the C language,\" SIGPLAN Notices 17:1, pp. 354-356. Suzuki, N. [1982]. \"Analysis of pointer 'rotation',\" Comm. ACM 25:5, pp. 330-335. Tarjan, R. E. [1972]. \"Depth first search and linear graph algorithms,\" SIAM J. Computing 1:2, pp. 146-160. Tarjan, R. E. [1975]. \"On the efficiency of a good but not linear set merging algorithm,\" J. ACM 22:2, pp. 215-225. Tarjan, R. E. [1981]. \"Minimum spanning trees,\" unpublished memorandum, Bell Laboratories, Murray Hill, N. J. Tarjan, R. E. [1983]. Data Structures and Graph Algorithms, unpublished manuscript, Bell Laboratories, Murray Hill, N. J. Ullman, J. D. [1974]. \"Fast algorithms for the elimination of common subexpressions,\" Acta Informatica 2:3, pp. 191-213. Ullman, J. D. [1982]. Principles of Database Systems, Computer Science Press, Rockville, Md. van Emde Boas, P., R. Kaas, and E. Zijlstra [1977]. \"Design and implementation of an efficient priority queue structure,\" Math Syst. Theory, 10, pp. 99-127. http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1213.htm (8 of 9) [1.7.2001 19:33:58]

Data Structures and Algorithms: Bibliography Warshall, S. [1962]. \"A theorem on Boolean matrices,\" J. ACM 9:1, pp. 11-12. Weinberg, G. M. [1971]. The Psychology of Computer Programming, Van Nostrand, N. Y. Weiner, P. [1973]. \"Linear pattern matching algorithms,\" Proc. IEEE Fourteenth Annual Symp. on Switching and Automata Theory, pp. 1-11. Wexelblat, R. L. (ed.) [1981]. History of Programming Languages, Academic Press, N. Y. Wiederhold, G. [1982]. Database Design, McGraw-Hill, New York. Williams, J. W. J. [1964]. \"Algorithm 232: Heapsort,\" Comm. ACM 7:6, pp. 347- 348. Wirth, N. [1973]. Systematic Programming: An Introduction, Prentice-Hall, Englewood Cliffs, N. J. Wirth, N. [1976]. Algorithms + Data Structures = Programs, Prentice-Hall, Englewood Cliffs, N. J. Wulf, W. A., M. Shaw, P. Hilfinger, and L. Flon [1981]. Fundamental Structures of Computer Science, Addison-Wesley, Reading, Mass. Yao, A. C. [1975]. \"An O(|E| log log |V|) algorithm for finding minimum spanning trees,\" Inf. Processing Letters 4:1, pp. 21-23. Yao, A. C., and F. F. Yao [1976]. \"The complexity of searching a random ordered table,\" Proc. IEEE Seventeenth Annual Symp. on Foundations of Computer Science, pp. 173-177. Yourdon, E., and L. L. Constantine [1975]. Structured Design, Yourdon, New York. Table of Contents http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1213.htm (9 of 9) [1.7.2001 19:33:58]

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_1.gif http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_1.gif [1.7.2001 19:34:07]

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_2.gif http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_2.gif [1.7.2001 19:34:15]

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_3.gif http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_3.gif [1.7.2001 19:34:23]

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_6.gif http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_6.gif [1.7.2001 19:34:40]

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_7.gif http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_7.gif [1.7.2001 19:34:55]

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_10.gif http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_10.gif [1.7.2001 19:35:10]

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_11.gif http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_11.gif [1.7.2001 19:35:22]

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_12.gif http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_12.gif [1.7.2001 19:35:30]

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_14.gif http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_14.gif [1.7.2001 19:35:42]

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_15.gif http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_15.gif [1.7.2001 19:35:51]

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_16.gif http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_16.gif [1.7.2001 19:36:07]

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_18.gif http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_18.gif [1.7.2001 19:36:17]

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_19.gif http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_19.gif [1.7.2001 19:36:20]

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_20.gif http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f12_20.gif [1.7.2001 19:36:24]