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

[2] G. M. Adel'son-Vel'skii 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] Alok Aggarwal and Jeffrey Scott Vitter. The input/output complexity of sorting and related problems. Communications of the ACM, 31(9): 1116–1127, 1988.

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

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

[7] Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.

[8] Ravindra K. Ahuja, Kurt Mehlhorn, James B. Orlin, and Robert E. Tarjan. Faster algorithms for the shortest path problem. Journal of the ACM, 37: 213–223, 1990.

[9] Ravindra K. Ahuja and James B. Orlin. A fast and simple algorithm for the maximum flow problem. Operations Research, 37(5): 748–759, 1989.

[10] Ravindra K. Ahuja, James B. Orlin, and Robert E. Tarjan. Improved time bounds for the maximum flow problem. SIAM Journal on Computing, 18(5): 939–954, 1989.

[11] Miklos Ajtai, János Komlós, and Endre Szemerédi. Sorting in c log n parallel steps. Combinatorica, 3: 1–19, 1983.

[12] Miklos Ajtai, Nimrod Megiddo, and Orli Waarts. Improved algorithms and analysis for secretary problems and generalizations. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pages 473–482, 1995.

[13] Mohamad Akra and Louay Bazzi. On the solution of linear recurrence equations. Computational Optimization and Applications, 10(2): 195–210, 1998.

[14] Noga Alon. Generating pseudo-random permutations and maximum flow algorithms. Information Processing Letters, 35: 201–204, 1990.

[15] Arne Andersson. Balanced search trees made simple. In Proceedings of the Third Workshop on Algorithms and Data Structures, number 709 in Lecture Notes in Computer Science, pages 60–71. Springer-Verlag, 1993.

[16] Arne Andersson. Faster deterministic sorting and searching in linear space. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science, pages 135–141, 1996.

[17] Arne Andersson, Torben Hagerup, Stefan Nilsson, and Rajeev Raman. Sorting in linear time? Journal of Computer and System Sciences, 57: 74–93, 1998.

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

[19] Sanjeev Arora. Probabilistic checking of proofs and the hardness of approximation problems. PhD thesis, University of California, Berkeley, 1994.

[20] Sanjeev Arora. Theapproximability of NP-hard problems. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pages 337–348, 1998.

[21] Sanjeev Arora. Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. Journal of the ACM, 45(5): 753–782, 1998.

[22] Sanjeev Arora and Carsten Lund. Hardness of approximations. In Dorit S. Hochbaum, editor, Approximation Algorithms for NP-Hard Problems, pages 399–446. PWS Publishing Company, 1997.

[23] Javed A. Aslam. A simple bound on the expected height of a randomly built binary search tree. Technical Report TR2001-387, Dartmouth College Department of Computer Science, 2001.

[24] Mikhail J. Atallah, editor. Algorithms and Theory of Computation Handbook. CRC Press, 1999.

[25] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer-Verlag, 1999.

[26] Sara Baase and Alan Van Gelder. Computer Algorithms: Introduction to Design and Analysis. Addison-Wesley, third edition, 2000.

[27] Eric Bach. Private communication, 1989.

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

[29] Eric Bach and Jeffery Shallit. Algorithmic Number Theory—Volume I: Efficient Algorithms. The MIT Press, 1996.

[30] David H. Bailey, King Lee, and Horst D. Simon. Using Strassen's algorithm to accelerate the solution of linear systems. The Journal of Supercomputing, 4(4): 357–371, 1990.

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

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

[33] 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.

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

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

[36] 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.

[37] Michael A. Bender, Erik D. Demaine, and Martin Farach-Colton. Cache-oblivious B-trees. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pages 399–409, 2000.

[38] Samuel W. Bent and John W. John. Finding the median requires 2n comparisons. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pages 213–216, 1985.

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

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

[41] 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.

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

[43] 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.

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

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

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

[47] Gilles Brassard and Paul Bratley. Fundamentals of Algorithmics. Prentice Hall, 1996.

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

[49] 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.

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

[51] J. P. Buhler, H. W. Lenstra, Jr., and Carl Pomerance. Factoring integers with the number field sieve. In A. K. Lenstra and H. W. Lenstra, Jr., editors, The Development of the Number Field Sieve, volume 1554 of Lecture Notes in Mathematics, pages 50–94. Springer-Verlag, 1993.

[52] J. Lawrence Carter and Mark N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2): 143–154, 1979.

[53] Bernard Chazelle. A minimum spanning tree algorithm with inverse-Ackermann type complexity. Journal of the ACM, 47(6): 1028–1047, 2000.

[54] Joseph Cheriyan and Torben Hagerup. A randomized maximum-flow algorithm. SIAM Journal on Computing, 24(2): 203–226, 1995.

[55] Joseph Cheriyan and S. N. Maheshwari. Analysis of preflow push algorithms for maximum network flow. SIAM Journal on Computing, 18(6): 1057–1086, 1989.

[56] Boris V. Cherkassky and Andrew V. Goldberg. On implementing the push-relabel method for the maximum flow problem. Algorithmica, 19(4): 390–410, 1997.

[57] Boris V. Cherkassky, Andrew V. Goldberg, and Tomasz Radzik. Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming, 73(2): 129–174, 1996.

[58] Boris V. Cherkassky, Andrew V. Goldberg, and Craig Silverstein. Buckets, heaps, lists and monotone priority queues. SIAM Journal on Computing, 28(4): 1326–1346, 1999.

[59] 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.

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

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

[62] V. Chvátal. Linear Programming. W. H. Freeman and Company, 1983.

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

[64] 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.

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

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

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

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

[69] Don Coppersmith. Modifications to the number field sieve. Journal of Cryptology, 6: 169–180, 1993.

[70] Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progression. Journal of Symbolic Computation, 9(3): 251–280, 1990.

[71] Thomas H. Cormen. Virtual Memory for Data-Parallel Computing. PhD thesis, Department of Electrical Engineering and Computer Science, MIT, 1992.

[72] Eric V. Denardo and Bennett L. Fox. Shortest-route methods: 1. Reaching, pruning, and buckets. Operations Research, 27(1): 161–186, 1979.

[73] Martin Dietzfelbinger, Anna Karlin, Kurt Mehlhorn, Friedhelm Meyer auf der Heide, Hans Rohnert, and Robert E. Tarjan. Dynamic perfect hashing: Upper and lower bounds. SIAM Journal on Computing, 23(4): 738–761, 1994.

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

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

[76] E. A. Dinic. Algorithm for solution of a problem of maximum flow in a network with power estimation. Soviet Mathematics Doklady, 11(5): 1277–1280, 1970.

[77] Brandon Dixon, Monika Rauch, and Robert E. Tarjan. Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM Journal on Computing, 21(6): 1184–1192, 1992.

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

[79] Dorit Dor and Uri Zwick. Selecting the median. In Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms, pages 28–37, 1995.

[80] Alvin W. Drake. Fundamentals of Applied Probability Theory. McGraw-Hill, 1967.

[81] 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.

[82] James R. Driscoll, Neil Sarnak, Daniel D. Sleator, and Robert E. Tarjan. Making data structures persistent. Journal of Computer and System Sciences, 38: 86–124, 1989.

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

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

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

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

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

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

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

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

[91] Robert W. Floyd. Permuting information in idealized two-level storage. In Raymond E. Miller and James W. Thatcher, editors, Complexity of Computer Computations, pages 105–109. Plenum Press, 1972.

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

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

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

[95] Michael L. Fredman. New bounds on the complexity of the shortest path problem. SIAM Journal on Computing, 5(1): 83–89, 1976.

[96] Michael L. Fredman, János Komlós, and Endre Szermerédi. Storing a sparse table with O(1) worst case access time. Journal of the ACM, 31(3): 538–544, 1984.

[97] 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.

[98] 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.

[99] Michael L. Fredman and Dan E. Willard. Surpassing the information theoretic bound with fusion trees. Journal of Computer and System Sciences, 47: 424–436, 1993.

[100] Michael L. Fredman and Dan E. Willard. Trans-dichotomous algorithms for minimum spanning trees and shortest paths. Journal of Computer and System Sciences, 48(3): 533–551, 1994.

[101] Harold N. Gabow. Path-based depth-first search for strong and biconnected components. Information Processing Letters, 74: 107–114, 2000.

[102] Harold N. Gabow, Z. Galil, T. Spencer, and Robert E. Tarjan. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica, 6(2): 109–122, 1986.

[103] 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.

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

[105] Zvi Galil and Oded Margalit. All pairs shortest distances for graphs with small integer length edges. Information and Computation, 134(2): 103–139, 1997.

[106] Zvi Galil and Oded Margalit. All pairs shortest paths for graphs with small integer length edges. Journal of Computer and System Sciences, 54(2): 243–254, 1997.

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

[108] Igal Galperin and Ronald L. Rivest. Scapegoat trees. In Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms, pages 165–174, 1993.

[109] Michael R. Garey, R. L. Graham, and J. D. Ullman. Worst-case analyis of memory allocation algorithms. In Proceedings of the Fourth Annual ACM Symposium on Theory of Computing, pages 143–150, 1972.

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

[111] Saul Gass. Linear Programming: Methods and Applications. International Thomson Publishing, fourth edition, 1975.

[112] Fanica 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.

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

[114] E. N. Gilbert and E. F. Moore. Variable-length binary encodings. Bell System Technical Journal, 38(4): 933–967, 1959.

[115] Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6): 1115–1145, 1995.

[116] Michel X. Goemans and David P. Williamson. The primal-dual method for approximation algorithms and its application to network design problems. In Dorit Hochbaum, editor, Approximation Algorithms for NP-Hard Problems, pages 144–191. PWS Publishing Company, 1997.

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

[118] Andrew V. Goldberg. Scaling algorithms for the shortest paths problem. SIAM Journal on Computing, 24(3): 494–504, 1995.

[119] Andrew V. Goldberg, Éva Tardos, and Robert E. Tarjan. Network flow algorithms. In Bernhard Korte, László Lovász, Hans Jürgen Prömel, and Alexander Schrijver, editors, Paths, Flows, and VLSI-Layout, pages 101–164. Springer-Verlag, 1990.

[120] Andrew V. Goldberg and Satish Rao. Beyond the flow decomposition barrier. Journal of the ACM, 45: 783–797, 1998.

[121] Andrew V. Goldberg and Robert E. Tarjan. A new approach to the maximum flow problem. Journal of the ACM, 35: 921–940, 1988.

[122] D. Goldfarb and M. J. Todd. Linear programming. In G. L. Nemhauser, A. H. G. Rinnooy-Kan, and M. J. Todd, editors, Handbook in Operations Research and Management Science, Vol. 1, Optimization, pages 73–170. Elsevier Science Publishers, 1989.

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

[124] 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.

[125] Gene H. Golub and Charles F. Van Loan. Matrix Computations. The Johns Hopkins University Press, third edition, 1996.

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

[127] Rafael C. Gonzalez and Richard E. Woods. Digital Image Processing. Addison-Wesley, 1992.

[128] Michael T. Goodrich and Roberto Tamassia. Data Structures and Algorithms in Java. John Wiley & Sons, 1998.

[129] Ronald L. Graham. Bounds for certain multiprocessor anomalies. Bell Systems Technical Journal, 45: 1563–1581, 1966.

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

[131] Ronald 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.

[132] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathematics. Addison-Wesley, second edition, 1994.

[133] David Gries. The Science of Programming. Springer-Verlag, 1981.

[134] M. Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, 1988.

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

[136] Dan Gusfield. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997.

[137] Yijie Han. Improved fast integer sorting in linear space. In Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms, pages 793–796, 2001.

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

[139] Gregory C. Harfst and Edward M. Reingold. A potential-based amortized analysis of the union-find data structure. SIGACT News, 31(3): 86–95, 2000.

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

[141] Michael T. Heideman, Don H. Johnson, and C. Sidney Burrus. Gauss and the history of the Fast Fourier Transform. IEEE ASSP Magazine, pages 14–21, 1984.

[142] Monika R. Henzinger and Valerie King. Fully dynamic biconnectivity and transitive closure. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pages 664–672, 1995.

[143] Monika R. Henzinger and Valerie King. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. Journal of the ACM, 46(4): 502–516, 1999.

[144] Monika R. Henzinger, Satish Rao, and Harold N. Gabow. Computing vertex connectivity: New bounds from old techniques. Journal of Algorithms, 34(2): 222–250, 2000.

[145] Nicholas J. Higham. Exploiting fast matrix multiplication within the level 3 BLAS. ACM Transactions on Mathematical Software, 16(4): 352–368, 1990.

[146] C. A. R. Hoare. Algorithm 63 (PARTITION) and algorithm 65 (FIND). Communications of the ACM, 4(7): 321–322, 1961.

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

[148] Dorit S. Hochbaum. Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Applied Math, 6: 243–254, 1983.

[149] Dorit S. Hochbaum, editor. Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, 1997.

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

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

[152] 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.

[153] John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, second edition, 2001.

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

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

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

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

[158] Ellis Horowitz, Sartaj Sahni, and Sanguthevar Rajasekaran. Computer Algorithms. Computer Science Press, 1998.

[159] T. C. Hu and M. T. Shing. Computation of matrix chain products. Part I. SIAM Journal on Computing, 11(2): 362–373, 1982.

[160] T. C. Hu and M. T. Shing. Computation of matrix chain products. Part II. SIAM Journal on Computing, 13(2): 228–251, 1984.

[161] T. C. Hu and A. C. Tucker. Optimal computer search trees and variable-length alphabetic codes. SIAM Journal on Applied Mathematics, 21(4): 514–532, 1971.

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

[163] Steven Huss-Lederman, Elaine M. Jacobson, Jeremy R. Johnson, Anna Tsao, and Thomas Turnbull. Implementation of Strassen's algorithm for matrix multiplication. In SC96 Technical Papers, 1996.

[164] 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.

[165] 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.

[166] David S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9: 256–278, 1974.

[167] David S. Johnson. The NP-completeness column: An ongoing guide—the tale of the second prover. Journal of Algorithms, 13(3): 502–524, 1992.

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

[169] David R. Karger, Philip N. Klein, and Robert E. Tarjan. A randomized linear-time algorithm to find minimum spanning trees. Journal of the ACM, 42(2): 321–328, 1995.

[170] David R. Karger, Daphne Koller, and Steven J. Phillips. Finding the hidden path: time bounds for all-pairs shortest paths. SIAM Journal on Computing, 22(6): 1199–1217, 1993.

[171] Howard Karloff. Linear Programming. Birkäuser, 1991.

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

[173] 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.

[174] Richard M. Karp. An introduction to randomized algorithms. Discrete Applied Mathematics, 34: 165–201, 1991.

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

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

[177] Valerie King. A simpler minimum spanning tree verification algorithm. Algorithmica, 18(2): 263–270, 1997.

[178] Valerie King, Satish Rao, and Robert E. Tarjan. A faster deterministic maximum flow algorithm. Journal of Algorithms, 17: 447–474, 1994.

[179] Jeffrey H. Kingston. Algorithms and Data Structures: Design, Correctness, Analysis. Addison-Wesley, 1990.

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

[181] Philip N. Klein and Neal E. Young. Approximation algorithms for NP-hard optimization problems. In CRC Handbook on Algorithms, pages 34-1–34-19. CRC Press, 1999.

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

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

[184] Donald E. Knuth. Optimum binary search trees. Acta Informatica, 1: 14–25, 1971.

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

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

[187] 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.

[188] J. Komlós. Linear verification for spanning trees. Combinatorica, 5(1): 57–65, 1985.

[189] Bernhard Korte and László 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.

[190] Bernhard Korte and László Lovász. Structural properties of greedoids. Combinatorica, 3: 359–374, 1983.

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

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

[193] Dexter C. Kozen. The Design and Analysis of Algorithms. Springer-Verlag, 1992.

[194] David W. Krumme, George Cybenko, and K. N. Venkataraman. Gossiping in minimal time. SIAM Journal on Computing, 21(1): 111–139, 1992.

[195] 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.

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

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

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

[199] Tom Leighton and Satish Rao. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 422–431, 1988.

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

[201] A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard. The number field sieve. In A. K. Lenstra and H. W. Lenstra, Jr., editors, The Development of the Number Field Sieve, volume 1554 of Lecture Notes in Mathematics, pages 11–42. Springer-Verlag, 1993.

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

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

[204] Harry R. Lewis and Christos H. Papadimitriou. Elements of the Theory of Computation. Prentice-Hall, second edition, 1998.

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

[206] László Lovász. On the ratio of optimal integral and fractional covers. Discrete Mathematics, 13: 383–390, 1975.

[207] László Lovász and M. D. Plummer. Matching Theory, volume 121 of Annals of Discrete Mathematics. North Holland, 1986.

[208] Bruce M. Maggs and Serge A. Plotkin. Minimum-cost spanning tree as a path-finding problem. Information Processing Letters, 26(6): 291–293, 1988.

[209] Michael Main. Data Structures and Other Objects Using Java. Addison-Wesley, 1999.

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

[211] Conrado Martínez and Salvador Roura. Randomized binary search trees. Journal of the ACM, 45(2): 288–323, 1998.

[212] 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.

[213] H. A. Maurer, Th. Ottmann, and H.-W. Six. Implementing dictionaries using binary trees of very small height. Information Processing Letters, 5(1): 11–14, 1976.

[214] Ernst W. Mayr, Hans Jürgen Prömel, and Angelika Steger, editors. Lectures on Proof Verification and Approximation Algorithms. Number 1367 in Lecture Notes in Computer Science. Springer-Verlag, 1998.

[215] C. C. McGeoch. All pairs shortest paths and the essential subgraph. Algorithmica, 13(5): 426–441, 1995.

[216] M. D. McIlroy. A killer adversary for quicksort. Software—Practice and Experience, 29(4): 341–344, 1999.

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

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

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

[220] Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1997.

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

[222] John C. Mitchell. Foundations for Programming Languages. MIT Press, 1996.

[223] Joseph S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM Journal on Computing, 28(4): 1298–1309, 1999.

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

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

[226] 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.

[227] Rajeev Motwani, Joseph (Seffi) Naor, and Prabakhar Raghavan. Randomized approximation algorithms in combinatorial optimization. In Dorit Hochbaum, editor, Approximation Algorithms for NP-Hard Problems, pages 447–481. PWS Publishing Company, 1997.

[228] Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge Unveristy Press, 1995.

[229] J. I. Munro and V. Raman. Fast stable in-place sorting with O (n) data moves. Algorithmica, 16(2): 151–160, 1996.

[230] J. Nievergelt and E. M. Reingold. Binary search trees of bounded balance. SIAM Journal on Computing, 2(1): 33–43, 1973.

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

[232] Alan V. Oppenheim and Ronald W. Schafer, with John R. Buck. Discrete-Time Signal Processing. Prentice-Hall, second edition, 1998.

[233] Alan V. Oppenheim and Alan S. Willsky, with S. Hamid Nawab. Signals and Systems. Prentice-Hall, second edition, 1997.

[234] James B. Orlin. A polynomial time primal network simplex algorithm for minimum cost flows. Mathematical Programming, 78(1): 109–129, 1997.

[235] Joseph O'Rourke. Computational Geometry in C. Cambridge University Press, 1993.

[236] Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.

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

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

[239] Michael S. Paterson. Progress in selection. In Proceedings of the Fifth Scandinavian Workshop on Algorithm Theory, pages 368–379, 1996.

[240] Pavel A. Pevzner. Computational Molecular Biology: An Algorithmic Approach. The MIT Press, 2000.

[241] Steven Phillips and Jeffery Westbrook. Online load balancing and network flow. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, pages 402–411, 1993.

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

[243] J. M. Pollard. Factoring with cubic integers. In A. K. Lenstra and H. W. Lenstra, Jr., editors, The Development of the Number Field Sieve, volume 1554 of Lecture Notes in Mathematics, pages 4–10. Springer, 1993.

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

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

[246] William K. Pratt. Digital Image Processing. John Wiley & Sons, second edition, 1991.

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

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

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

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

[251] William Pugh. Skip lists: A probabilistic alternative to balanced trees. Communications of the ACM, 33(6): 668–676, 1990.

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

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

[254] Michael O. Rabin. Probabilistic algorithm for testing primality. Journal of Number Theory, 12(1): 128–138, 1980.

[255] P. Raghavan and C. D. Thompson. Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica, 7: 365–374, 1987.

[256] Rajeev Raman. Recent results on the single-source shortest paths problem. SIGACT News, 28(2): 81–87, 1997.

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

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

[259] 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.

[260] Herbert Robbins. A remark on Stirling's formula. American Mathematical Monthly, 62(1): 26–29, 1955.

[261] 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.

[262] Salvador Roura. An improved master theorem for divide-and-conquer recurrences. In Proceedings of Automata, Languages and Programming, 24th International Colloquium, ICALP'97, pages 449–459, 1997.

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

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

[265] A. Schönhage, M. Paterson, and N. Pippenger. Finding the median. Journal of Computer and System Sciences, 13(2): 184–199, 1976.

[266] Alexander Schrijver. Theory of linear and integer programming. John Wiley & Sons, 1986.

[267] Alexander Schrijver. Paths and flows—a historical survey. CWI Quarterly, 6: 169–183, 1993.

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

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

[270] Raimund Seidel. On the all-pairs-shortest-path problem in unweighted undirected graphs. Journal of Computer and System Sciences, 51(3): 400–403, 1995.

[271] Raimund Seidel and C. R. Aragon. Randomized search trees. Algorithmica, 16: 464–497, 1996.

[272] Joao Setubal and Joao Meidanis. Introduction to Computational Molecular Biology. PWS Publishing Company, 1997.

[273] Clifford A. Shaffer. A Practical Introduction to Data Structures and Algorithm Analysis. Prentice Hall, second edition, 2001.

[274] Jeffrey Shallit. Origins of the analysis of the Euclidean algorithm. Historia Mathematica, 21(4): 401–419, 1994.

[275] Michael I. Shamos and Dan Hoey. Geometric intersection problems. In Proceedings of the 17th Annual Symposium on Foundations of Computer Science, pages 208–215, 1976.

[276] M. Sharir. A strong-connectivity algorithm and its applications in data flow analysis. Computers and Mathematics with Applications, 7: 67–72, 1981.

[277] David B. Shmoys. Computing near-optimal solutions to combinatorial optimization problems. In William Cook, László Lovász, and Paul Seymour, editors, Combinatorial Optimization, volume 20 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 1995.

[278] Avi Shoshan and Uri Zwick. All pairs shortest paths in undirected graphs with integer weights. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, pages 605–614, 1999.

[279] Michael Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.

[280] Steven S. Skiena. The Algorithm Design Manual. Springer-Verlag, 1998.

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

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

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

[284] Daniel A. Spielman and Shang-Hua Teng. The simplex algorithm usually takes a polynomial number of steps. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, 2001.

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

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

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

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

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

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

[291] 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.

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

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

[294] Robert E. Tarjan. Class notes: Disjoint set union. COS 423, Princeton University, 1999.

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

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

[297] Mikkel Thorup. Faster determinstic sorting and priority queues in linear space. In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, pages 550–555, 1998.

[298] Mikkel Thorup. Undirected single-source shortest paths with positive integer weights in linear time. Journal of the ACM, 46(3): 362–394, 1999.

[299] Mikkel Thorup. On RAM priority queues. SIAM Journal on Computing, 30(1): 86–109, 2000.

[300] Richard Tolimieri, Myoung An, and Chao Lu. Mathematics of Multidimensional Fourier Transform Algorithms. Springer-Verlag, second edition, 1997.

[301] 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.

[302] Jan van Leeuwen, editor. Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity. Elsevier Science Publishers and The MIT Press, 1990.

[303] Charles Van Loan. Computational Frameworks for the Fast Fourier Transform. Society for Industrial and Applied Mathematics, 1992.

[304] Robert J. Vanderbei. Linear Programming: Foundations and Extensions. Kluwer Academic Publishers, 1996.

[305] Vijay V. Vazirani. Approximation Algorithms. Springer-Verlag, 2001.

[306] Rakesh M. Verma. General techniques for analyzing recursive algorithms with applications. SIAM Journal on Computing, 26(2): 568–581, 1997.

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

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

[309] Michael S. Waterman. Introduction to Computational Biology, Maps, Sequences and Genomes. Chapman & Hall, 1995.

[310] Mark Allen Weiss. Data Structures and Algorithm Analysis in C++. Addison-Wesley, 1994.

[311] Mark Allen Weiss. Algorithms, Data Structures and Problem Solving with C++. Addison-Wesley, 1996.

[312] Mark Allen Weiss. Data Structures and Problem Solving Using Java. Addison-Wesley, 1998.

[313] Mark Allen Weiss. Data Structures and Algorithm Analysis in Java. Addison-Wesley, 1999.

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

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

[316] J. W. J. Williams. Algorithm 232 (HEAPSORT). Communications of the ACM, 7: 347–348, 1964.

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

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

[319] Yinyu Ye. Interior Point Algorithms: Theory and Analysis. John Wiley & Sons, 1997.

[320] Daniel Zwillinger, editor. CRC Standard Mathematical Tables and Formulae. CRC Press, 30th edition, 1996.