BIBLIOGRAPHY

[1] Milton Abramowitz and Irene A. Stegun, editors. Handbook of Mathematical Functions. Dover, 1965.

[2] G. M. and E. M. Landis. An algorithm for the organization of information. Soviet Mathematics Doklady, 3: 1259-1263, 1962.

[3] Leonard M. Adleman, Carl Pomerance, and Robert S. Rumely. On distinguishing prime numbers from composite numbers. Annals of Mathematics, 117: 173-206, 1983.

[4] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.

[5] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. Data Structures and Algorithms. Addison-Wesley, 1983.

[6] Ravindra K. Ahuja, Kurt Mehlhorn, James B. Orlin, and Robert E. Tarjan. Faster algorithms for the shortest path problem. Technical Report 193, MIT Operations Research Center, 1988.

[7] Howard H. Aiken and Grace M. Hopper. The automatic sequence controlled calculator. In Brian Randell, editor, The Origins of Digital Computers, pages 203-222. Springer-Verlag, third edition, 1982.

[8] M. Ajtai, J. Komlós, and E. Szemerédi. An O(n log n) sorting network. InProceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pages 1-9, 1983.

[9] Selim G. Akl. The Design and Analysis of Parallel Algorithms. Prentice-Hall, 1989.

[10] Richard J. Anderson and Gary L. Miller. Deterministic parallel list ranking. In John H. Reif, editor, 1988 Aegean Workshop on Computing, volume 319 of Lecture Notes in Computer Science, pages 81-90. Springer-Verlag, 1988.

[11] Richard J. Anderson and Gary L. Miller. A simple randomized parallel algorithm for list-ranking. Unpublished manuscript, 1988.

[12] Tom M. Apostol. Calculus, volume 1. Blaisdell Publishing Company, second edition, 1967.

[13] A. J. Atrubin. A one-dimensional real-time iterative multiplier. IEEE Transactions on Electronic Computers, EC-14(1):394-399, 1965.

[14] Sara Baase. Computer Algorithms: Introduction to Design and Analysis. Addison-Wesley, second edition, 1988.

[15] Eric Bach. Private communication, 1989.

[16] Eric Bach. Number-theoretic algorithms. In Annual Review of Computer Science, volume 4, pages 119- 172. Annual Reviews, Inc., 1990.

[17] R. Bayer. Symmetric binary B-trees: Data structure and maintenance algorithms. Acta Informatica, 1:290-306, 1972.

[18] R. Bayer and E. M. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1(3):173-189, 1972.

[19] Paul W. Beame, Stephen A. Cook, and H. James Hoover. Log depth circuits for division and related problems. SIAM Journal on Computing, 15(4):994-1003, 1986.

[20] Pierre Beauchemin, Gilles Brassard, Claude Crépeau, Claude Goutier, and Carl Pomerance. The generation of random numbers that are probably prime. Journal of Cryptology, 1:53-64, 1988.

[21] Richard Bellman. Dynamic Programming. Princeton University Press, 1957.

[22] Richard Bellman. On a routing problem. Quarterly of Applied Mathematics, 16(1):87-90, 1958.

[23] Michael Ben-Or. Lower bounds for algebraic computation trees. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pages 80-86, 1983.

[24] Jon L. Bentley. Writing Efficient Programs. Prentice-Hall, 1982.

[25] Jon L. Bentley. Programming Pearls. Addison-Wesley, 1986.

[26] Jon L. Bentley, Dorothea Haken, and James B. Saxe. A general method for solving divide-and-conquer recurrences. SIGACT News, 12(3):36-44, 1980.

[27] William H. Beyer, editor. CRC Standard Mathematical Tables. The Chemical Rubber Company, 1984.

[28] Patrick Billingsley. Probability and Measure. John Wiley & Sons, second edition, 1986.

[29] Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert E. Tarjan. Time bounds for selection. Journal of Computer and System Sciences, 7(4):448-461, 1973.

[30] Béla Bollobás. Random Graphs. Academic Press, 1985.

[31] J. A. Bondy and U. S. R. Murty. Graph Theory with Applications. American Elsevier, 1976.

[32] Robert S. Boyer and J. Strother Moore. A fast string-searching algorithm. Communications of the ACM, 20(10):762-772, 1977.

[33] Gilles Brassard and Paul Bratley. Algorithmics: Theory and Practice. Prentice-Hall, 1988.

[34] Richard P. Brent. The parallel evaluation of general arithmetic expressions. Journal of the ACM, 21(2):201-206, 1974.

[35] Richard P. Brent. An improved Monte Carlo factorization algorithm. BIT, 20(2):176-184, 1980.

[36] Mark R. Brown. The Analysis of a Practical and Nearly Optimal Priority Queue. PhD thesis, Computer Science Department, Stanford University, 1977. Technical Report STAN-CS-77-600.

[37] Mark R. Brown. Implementation and analysis of binomial queue algorithms. SIAM Journal on Computing, 7(3):298-319, 1978.

[38] Arthur W. Burks, editor. Theory of Self-Reproducing Automata. University of Illinois Press, 1966.

[39] Joseph J. F. Cavanagh. Digital Computer Arithmetic. McGraw-Hill, 1984.

[40] H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Mathematical Statistics, 23:493-507, 1952.

[41] Kai Lai Chung. Elementary Probability Theory with Stochastic Processes. Springer-Verlag, 1974.

[42] V. Chvátal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4(3):233-235, 1979.

[43] V. Chvátal, D. A. Klarner, and D. E. Knuth. Selected combinatorial research problems. Technical Report STAN-CS-72-292, Computer Science Department, Stanford University, 1972.

[44] Alan Cobham. The intrinsic computational difficulty of functions. In Proceedings of the 1964 Congress for Logic, Methodology, and the Philosophy of Science, pages 24-30. North-Holland, 1964.

[45] H. Cohen and H. W. Lenstra, Jr. Primality testing and jacobi sums. Mathematics of Computation, 42(165):297-330, 1984.

[46] Richard Cole. Parallel merge sort. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science, pages 511-516. IEEE Computer Society, 1986.

[47] Richard Cole and Uzi Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control, 70(1):32-53, 1986.

[48] D. Comer. The ubiquitous B-tree. ACM Computing Surveys, 11(2):121-137, 1979.

[49] Stephen Cook. The complexity of theorem proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing, pages 151-158, 1971.

[50] Stephen Cook, Cynthia Dwork, and Rüdiger Reischuk. Upper and lower time bounds for parallel random access machines without simultaneous writes. SIAM Journal on Computing, 15(1):87-97, 1986.

[51] James W. Cooley and John W. Tukey. An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation, 19(90): 297-301, April 1965.

[52] Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pages 1-6, 1987.

[53] George B. Dantzig. Linear Programming and Extensions. Princeton University Press, 1963.

[54] Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, IT-22(6):644-654, 1976.

[55] E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269-271, 1959.

[56] John D. Dixon. Factorization and primality tests. The American Mathematical Monthly, 91(6):333-352, 1984.

[57] Alvin W. Drake. Fundamentals of Applied Probability Theory. McGrawHill, 1967.

[58] James R. Driscoll, Harold N. Gabow, Ruth Shrairman, and Robert E. Tarjan. Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation. Communications of the ACM, 31(11):1343-1354, 1988.

[59] James R. Driscoll, Neil Sarnak, Daniel D. Sleator, and Robert E. Tarjan. Making data structures persistent. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, pages 109-121, 1986.

[60] Herbert Edelsbrunner. Algorithms in Combinatorial Geometry, volume 10 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag, 1987.

[61] Jack Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449-467, 1965.

[62] Jack Edmonds. Matroids and the greedy algorithm. Mathematical Programming, 1:126-136, 1971.

[63] Jack Edmonds and Richard M. Karp. Theoretical improvements in the algorithmic efficiency for network flow problems. Journal of the ACM, 19:248-264, 1972.

[64] G. Estrin, B. Gilchrist, and J. H. Pomerene. A note on high-speed digital multiplication. IRE Transactions on Electronic Computers, 5(3):140, 1956.

[65] Shimon Even. Graph Algorithms. Computer Science Press, 1979.

[66] William Feller. An Introduction to Probability Theory and Its Applications. John Wiley & Sons, third edition, 1968.

[67] M. J. Fischer and A. R. Meyer. Boolean matrix multiplication and transitive closure. In Proceedings of the Twelfth Annual Symposium on Switching and Automata Theory, pages 129-131. IEEE Computer Society, 1971.

[68] Robert W. Floyd. Algorithm 97 (SHORTEST PATH). Communications of the ACM, 5(6):345, 1962.

[69] Robert W. Floyd. Algorithm 245 (TREESORT). Communications of the ACM, 7:701, 1964.

[70] Robert W. Floyd and Ronald L. Rivest. Expected time bounds for selection. Communications of the ACM, 18(3):165-172, 1975.

[71] Lestor R. Ford, Jr., and D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962.

[72] Lestor R. Ford, Jr., and Selmer M. Johnson. A tournament problem. The American Mathematical Monthly, 66:387-389, 1959.

[73] Steven Fortune and James Wyllie. Parallelism in random access machines. In Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pages 114-118, 1978.

[74] Michael L. Fredman and Michael E. Saks. The cell probe complexity of dynamic data structures. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, 1989.

[75] Michael L. Fredman and Robert E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3):596-615, 1987.

[76] Harold N. Gabow and Robert E. Tarjan. A linear-time algorithm for a special case of disjoint set union. Journal of Computer and System Sciences, 30(2):209-221, 1985.

[77] Harold N. Gabow and Robert E. Tarjan. Faster scaling algorithms for network problems. SIAM Journal on Computing, 18(5):1013-1036, 1989.

[78] Zvi Galil and Joel Seiferas. Time-space-optimal string matching. Journal of Computer and System Sciences, 26(3):280-294, 1983.

[79] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.

[80] Gavril. Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM Journal on Computing, 1(2):180-187, 1972.

[81] Alan George and Joseph W-H Liu. Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall, 1981.

[82] Andrew V. Goldberg. Efficient Graph Algorithms for Sequential and Parallel Computers. PhD thesis, Department of Electrical Engineering and Computer Science, MIT, 1987.

[83] Andrew V. Goldberg, ...va Tardos, and Robert E. Tarjan. Network flow algorithms. Technical Report STAN-CS-89-1252, Computer Science Department, Stanford University, 1989.

[84] Andrew V. Goldberg and Serge A. Plotkin. Parallel ( + 1) coloring of constant-degree graphs. Information Processing Letters, 25(4):241-245, 1987.

[85] Andrew V. Goldberg and Robert E. Tarjan. A new approach to the maximum flow problem. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, pages 136-146, 1986.

[86] Shafi Goldwasser and Silvio Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270-299, 1984.

[87] Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1):186-208, 1989.

[88] Shafi Goldwasser, Silvio Micali, and Ronald L. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on Computing, 17(2):281-308, 1988.

[89] Gene H. Golub and Charles F. Van Loan. Matrix Computations. The Johns Hopkins University Press, 1983.

[90] G. H. Gonnet. Handbook of Algorithms and Data Structures. Addison-Wesley, 1984.

[91] R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters, 1:132-133, 1972.

[92] R. L. Graham and Pavol Hell. On the history of the minimum spanning tree problem. Annals of the History of Computing, 7(1):43-57, 1985.

[93] Leo J. Guibas and Robert Sedgewick. A diochromatic framework for balanced trees. In Proceedings of the 19th Annual Symposium on Foundations of Computer Science, pages 8-21. IEEE Computer Society, 1978.

[94] Frank Harary. Graph Theory. Addison-Wesley, 1969.

[95] J. Hartmanis and R. E. Stearns. On the computational complexity of algorithms. Transactions of the American Mathematical Society, 117:285-306, 1965.

[96] Frederick J. Hill and Gerald R. Peterson. Introduction to Switching Theory and Logical Design. John Wiley & Sons, second edition, 1974.

[97] C. A. R. Hoare. Algorithm 63 (partition) and algorithm 65 (find). Communications of the ACM, 4(7):321-322, 1961.

[98] C. A. R. Hoare. Quicksort. Computer Journal, 5(1):10-15, 1962.

[99] W. Hoeffding. On the distribution of the number of successes in independent trials. Annals of Mathematical Statistics, 27:713-721, 1956.

[100] Micha Hofri. Probabilistic Analysis of Algorithms. Springer-Verlag, 1987.

[101] John E. Hopcroft and Richard M. Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2(4):225-231, 1973.

[102] John E. Hopcroft and Robert E. Tarjan. Efficient algorithms for graph manipulation. Communications of the ACM, 16(6):372-378, 1973.

[103] John E. Hopcroft and Jeffrey D. Ullman. Set merging algorithms. SIAM Journal on Computing, 2(4):294-303, 1973.

[104] John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.

[105] Ellis Horowitz and Sartaj Sahni. Fundamentals of Computer Algorithms. Computer Science Press, 1978.

[106] T. C. Hu and M. T. Shing. Some theorems about matrix multiplication. In Proceedings of the 21st Annual Symposium on Foundations of Computer Science, pages 28-35. IEEE Computer Society, 1980.

[107] David A. Huffman. A method for the construction of minimum-redundancy codes. Proceedings of the IRE, 40(9):1098-1101, 1952.

[108] Kai Hwang. Computer Arithmetic: Principles, Architecture, and Design. John Wiley & Sons, 1979.

[109] Kai Hwang and Fayé A. Briggs. Computer Architecture and Parallel Processing. McGraw-Hill, 1984.

[110] Kai Hwang and Doug DeGroot. Parallel Processing for Supercomputers and Artificial Intelligence. McGraw-Hill, 1989.

[111] Oscar H. Ibarra and Chul E. Kim. Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM, 22(4):463-468, 1975.

[112] R. A. Jarvis. On the identification of the convex hull of a finite set of points in the plane. Information Processing Letters, 2:18-21, 1973.

[113] D. S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9:256-278, 1974.

[114] Donald B. Johnson. Efficient algorithms for shortest paths in sparse networks. Journal of the ACM, 24(1):1-13, 1977.

[115] N. Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica, 4(4):373-395, 1984.

[116] Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, Complexity of Computer Computations, pages 85-103. Plenum Press, 1972.

[117] Richard M. Karp and Michael O. Rabin. Efficient randomized pattern-matching algorithms. Technical Report TR-31-81, Aiken Computation Laboratory, Harvard University, 1981.

[118] Richard M. Karp and Vijaya Ramachandran. A survey of parallel algorithms for shared-memory machines. Technical Report UCB/CSD 88/408, Computer Science Division (EECS), University of California, Berkeley, 1988.

[119] A. V. Karzanov. Determining the maximal flow in a network by the method of preflows. Soviet Mathematics Doklady, 15:434-437, 1974.

[120] D. G. Kirkpatrick and R. Seidel. The ultimate planar convex hull algorithm? SIAM Journal on Computing, 15(2):287-299, 1986.

[121] Donald E. Knuth. Fundamental Algorithms, volume 1 of The Art of Computer Programming. Addison-Wesley, 1968. Second edition, 1973.

[122] Donald E. Knuth. Seminumerical Algorithms, volume 2 of The Art of Computer Programming. Addison-Wesley, 1969. Second edition, 1981.

[123] Donald E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley, 1973.

[124] Donald E. Knuth. Big omicron and big omega and big theta. ACM SIGACT News, 8(2):18-23, 1976.

[125] Donald E. Knuth, James H. Morris, Jr., and Vaughan R. Pratt. Fast pattern matching in strings. SIAM Journal on Computing, 6(2):323-350, 1977.

[126] Zvi Kohavi. Switching and Finite Automata Theory. McGraw-Hill, 1970.

[127] Bernhard Korte and Lászlo Lovász. Mathematical structures underlying greedy algorithms. In F. Gecseg, editor, Fundamentals of Computation Theory, number 117 in Lecture Notes in Computer Science, pages 205-209. Springer-Verlag, 1981.

[128] Bernhard Korte and Lászlo Lovász. Structural properties of greedoids. Combinatorica, 3:359-374, 1983.

[129] Bernhard Korte and Lászlo Lovász. Greedoids--a structural framework for the greedy algorithm. In W. Pulleybank, editor, Progress in Combinatorial Optimization, pages 221-243. Academic Press, 1984.

[130] Bernhard Korte and Lászlo Lovász. Greedoids and linear objective functions. SIAM Journal on Algebraic and Discrete Methods, 5(2):229-238, 1984.

[131] J. B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7:48-50, 1956.

[132] Eugene L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston, 1976.

[133] Eugene L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, editors. The Traveling Salesman Problem. John Wiley & Sons, 1985.

[134] C. Y. Lee. An algorithm for path connection and its applications. IRE Transactions on Electronic Computers, EC-10(3):346-365, 1961.

[135] F. Thomson Leighton. Introduction to Parallel Algorithms and Architectures: Networks and Algorithms. Morgan-Kaufmann, in preparation.

[136] Debra A. Lelewer and Daniel S. Hirschberg. Data compression. ACM Computing Surveys, 19(3):261-296, 1987.

[137] H. W. Lenstra, Jr. Factoring integers with elliptic curves. Annals of Mathematics, 126:649-673, 1987.

[138] L. A. Levin. Universal sorting problems. Problemy Peredachi Informatsii, 9(3):265-266, 1973. In Russian.

[139] Harry R. Lewis and Christos H. Papadimitriou. Elements of the Theory of Computation. Prentice-Hall, 1981.

[140] C. L. Liu. Introduction to Combinatorial Mathematics. McGraw-Hill, 1968.

[141] Lászlo Lovász. On the ratio of optimal integral and fractional covers. Discrete Mathematics, 13:383-390, 1975.

[142] Udi Manber. Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1989.

[143] William J. Masek and Michael S. Paterson. A faster algorithm computing string edit distances. Journal of Computer and System Sciences, 20(1):18-31, 1980.

[144] Kurt Mehlhorn. Sorting and Searching, volume 1 of Data Structures and Algorithms. Springer-Verlag, 1984.

[145] Kurt Mehlhorn. Graph Algorithms and NP-Completeness, volume 2 of Data Structures and Algorithms. Springer-Verlag, 1984.

[146] Kurt Mehlhorn. Multidimensional Searching and Computational Geometry, volume 3 of Data Structures and Algorithms. Springer-Verlag, 1984.

[147] Gary L. Miller. Riemann's hypothesis and tests for primality. Journal of Computer and System Sciences, 13(3):300-317, 1976.

[148] Louis Monier. Algorithmes de Factorisation D'Entiers. PhD thesis, L'Université Paris-Sud, Centre D'Orsay, 1980.

[149] Louis Monier. Evaluation and comparison of two efficient probabilistic primality testing algorithms. Theoretical Computer Science, 12(1): 97-108, 1980.

[150] Edward F. Moore. The shortest path through a maze. In Proceedings of the International Symposium on the Theory of Switching, pages 285-292. Harvard University Press, 1959.

[151] Ivan Niven and Herbert S. Zuckerman. An Introduction to the Theory of Numbers. John Wiley & Sons, fourth edition, 1980.

[152] Yu. Ofman. On the algorithmic complexity of discrete functions. Soviet Physics Doklady, 7(7):589-591, 1963. English translation.

[153] Alan V. Oppenheim and Alan S. Willsky, with Ian T. Young. Signals and Systems. Prentice-Hall, 1983.

[154] Christos H. Papadimitriou and Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, 1982.

[155] Michael S. Paterson, 1974. Unpublished lecture, Ile de Berder, France.

[156] J. M. Pollard. A Monte Carlo method for factorization. BIT, 15:331-334, 1975.

[157] Carl Pomerance. On the distribution of pseudoprimes. Mathematics of Computation, 37(156):587-593, 1981.

[158] Carl Pomerance. The quadratic sieve factoring algorithm. In T. Beth, N. Cot, and I. Ingemarrson, editors, Advances in Cryptology, volume 209 of Lecture Notes in Computer Science, pages 169-182. Springer-Verlag, 1984.

[159] Carl Pomerance, editor. Proceedings of the AMS Symposia in Applied Mathematics: Computational Number Theory and Cryptography. American Mathematical Society, to appear.

[160] Franco P. Preparata and Micheal Ian Shamos. Computational Geometry: An Introduction. Springer-Verlag, 1985.

[161] William H. Press, Brian P. Flannery, Saul A. Teukolsky, and William T. Vetterling. Numerical Recipes: The Art of Scientific Computing. Cambridge University Press, 1986.

[162] William H. Press, Brian P. Flannery, Saul A. Teukolsky, and William T. Vetterling. Numerical Recipes in C. Cambridge University Press, 1988.

[163] R. C. Prim. Shortest connection networks and some generalizations. Bell System Technical Journal, 36:1389-1401, 1957.

[164] Paul W. Purdom, Jr., and Cynthia A. Brown. The Analysis of Algorithms. Holt, Rinehart, and Winston, 1985.

[165] Michael O. Rabin. Probabilistic algorithms. In J. F. Traub, editor, Algorithms and Complexity: New Directions and Recent Results, pages 21-39. Academic Press, 1976.

[166] Michael O. Rabin. Probabilistic algorithm for testing primality. Journal of Number Theory, 12:128-138, 1980.

[167] Edward M. Reingold, Jürg Nievergelt, and Narsingh Deo. Combinatorial Algorithms: Theory and Practice. Prentice-Hall, 1977.

[168] Hans Riesel. Prime Numbers and Computer Methods for Factorization. Progress in Mathematics. Birkhäuser, 1985.

[169] Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120-126, 1978. See also U.S. Patent 4,405,829.

[170] D. J. Rosenkrantz, R. E. Stearns, and P. M. Lewis. An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing, 6:563-581, 1977.

[171] Y. A. Rozanov. Probability Theory: A Concise Course. Dover, 1969.

[172] S. Sahni and T. Gonzalez. P-complete approximation problems. Journal of the ACM, 23:555-565, 1976.

[173] John E. Savage. The Complexity of Computing. John Wiley & Sons, 1976.

[174] Robert Sedgewick. Implementing quicksort programs. Communications of the ACM, 21(10):847-857, 1978.

[175] Robert Sedgewick. Algorithms. Addison-Wesley, second edition, 1988.

[176] Michael I. Shamos and Dan Hoey. Geometric intersection problems. In Proceedings of the 16th Annual Symposium on Foundations of Computer Science, pages 208-215. IEEE Computer Society, 1975.

[177] Daniel D. Sleator and Robert E. Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3):362-391, 1983.

[178] Daniel D. Sleator and Robert E. Tarjan. Self-adjusting binary search trees. Journal of the ACM, 32(3):652-686, 1985.

[179] Joel Spencer. Ten Lectures on the Probabilistic Method. Regional Conference Series on Applied Mathematics (No. 52). SIAM, 1987.

[180] Staff of the Computation Laboratory. Description of a Relay Calculator, volume XXIV of The Annals of the Computation Laboratory of Harvard University. Harvard University Press, 1949.

[181] Gilbert Strang. Introduction to Applied Mathematics. Wellesley-Cambridge Press, 1986.

[182] Gilbert Strang. Linear Algebra and Its Applications. Harcourt Brace Jovanovich, third edition, 1988.

[183] Volker Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 14(3):354-356, 1969.

[184] T. G. Szymanski. A special case of the maximal common subsequence problem. Technical Report TR-170, Computer Science Laboratory, Princeton University, 1975.

[185] Robert E. Tarjan. Depth first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146-160, 1972.

[186] Robert E. Tarjan. Efficiency of a good but not linear set union algorithm. Journal of the ACM, 22(2):215-225, 1975.

[187] Robert E. Tarjan. A class of algorithms which require nonlinear time to maintain disjoint sets. Journal of Computer and System Sciences, 18(2):110-127, 1979.

[188] Robert E. Tarjan. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, 1983.

[189] Robert E. Tarjan. Amortized computational complexity. SIAM Journal on Algebraic and Discrete Methods, 6(2):306-318, 1985.

[190] Robert E. Tarjan and Jan van Leeuwen. Worst-case analysis of set union algorithms. Journal of the ACM, 31(2):245-281, 1984.

[191] Robert E. Tarjan and Uzi Vishkin. An efficient parallel biconnectivity algorithm. SIAM Journal on Computing, 14(4):862-874, 1985.

[192] George B. Thomas, Jr., and Ross L. Finney. Calculus and Analytic Geometry. Addison-Wesley, seventh edition, 1988.

[193] Leslie G. Valiant. Parallelism in comparison problems. SIAM Journal on Computing, 4(3):348-355, 1975.

[194] P. van Emde Boas. Preserving order in a forest in less than logarithmic time. In Proceedings of the 16th Annual Symposium on Foundations of Computer Science pages 75-84. IEEE Computer Society, 1975.

[195] Uzi Vishkin. Implementation of simultaneous memory address access in models that forbid it. Journal of Algorithms, 4(1):45-50, 1983.

[196] Jean Vuillemin. A data structure for manipulating priority queues. Communications of the ACM, 21(4):309-315, 1978.

[197] C. S. Wallace. A suggestion for a fast multiplier. IEEE Transactions on Electronic Computers, EC-13(1):14-17, 1964.

[198] Stephen Warshall. A theorem on boolean matrices. Journal of the ACM, 9(1):11-12, 1962.

[199] A. Weinberger and J. L. Smith. A one-microsecond adder using one-megacycle circuitry. IRE Transactions on Electronic Computers, EC-5(2), 1956.

[200] Hassler Whitney. On the abstract properties of linear dependence. American Journal of Mathematics, 57:509-533, 1935.

[201] Herbert S. Wilf. Algorithms and Complexity. Prentice-Hall, 1986.

[202] J. W. J. Williams. Algorithm 232 (heapsort). Communications of the ACM, 7:347-348, 1964.

[203] S. Winograd. On the algebraic complexity of functions. In Actes du Congrès International des Mathèmaticiens, volume 3, pages 283-288, 1970.

[204] James C. Wyllie. The Complexity of Parallel Computations. PhD thesis, Department of Computer Science, Cornell University, 1979.

[205] Andrew C.-C. Yao. A lower bound to finding convex hulls. Journal of the ACM, 28(4):780-787, 1981.