## <a class="calibre17">References</a> Adel'son-Vel'skii, G.M., and E. M. Landis. 1962 *“An algorithm for the organization of information.”* *Doklady Akademii Nauk SSSR* Vol. 146: 263–266. Agrawal, A., , N. Kayal, and , and N. Saxena. 2002. Not yet published. Available at <http://www.cse.iitk.ac.in/news/primality.html>. Akl, S. 1985 *Parallel sorting.* Orlando, Fl.: Academic Press. Aldous, D., and , and P. Diaconis. 1986 *“Shuffling cards and stopping times.”* *The American Mathematical Monthly* Vol. 93: 333–347. Apostol, T. M. 1997 *Introduction to analytic number theory.* New York: Springer-Verlag. Baker, R. C., and , and G. Harman. 1996 *The Brun-Titchmarsh Theorem on average. Proceedings of a conference in honor of Heini Halberstam* Vol. 1: 39–103. Bayer, R., and , and C. McCreight. 1972 *“Organization and maintenance of large ordered indexes.”* *Acta Informatica* Vol. 1, no. 3: 173–189. Bentley, J. L., , D. Haken, and , and J. B. Saxe. 1980. *“A general method for solving divide-and-conquer recurrences.”* *SIGACT News* Vol. 12, no. 3: 36–44. Blum, M., , R. W. Floyd, , V. Pratt, , R. L. Rivest, and , and R. E. Tarjan. 1973. *“Time bounds for selection.”* *Journal of Computer and System Sciences* Vol. 7, no. 4: 448–461. Borodin, A. B., and , and J. I. Munro. 1975. *The computational complexity of algebraic and numeric problems.* New York: American Elsevier. Brassard, G. 1985. *“Crusade for better notation.”* *SIGACT News* Vol. 17, no. 1: 60–64. Brassard, G., and , and P. Bratley. 1988. *Algorithmics: Theory and practice.* Englewood Cliffs, N.J.: Prentice Hall. Brassard, G., , S. Monet, and , and D. Zuffellato. 1986. *“L'arithmétique des très grands entiers.”* *TSI: Technique et Science Informatiques* Vol. 5, no. 2: 89–102. Chacian, L. G. 1979. *“A polynomial algorithm for linear programming.”* *Doklady Adad. Nauk U.S.S.R. 224* Vol. no. 5: 1093–1096. Clemen, R.T. 1991. *Making hard decisions.* Boston: PWS-Kent. Cook, S. A. 1971. *“The complexity of theorem proving procedures.”* *Proceedings of 3rd annual ACM symposium on the theory of computing,* 151–158. New York: ACM. Cooper, G. F. 1984. *“"NESTOR": A computer-based medical diagnostic that integrates causal and probabilistic knowledge.”* *Technical Report HPP-84–48,* Stanford Cal.: Stanford University. Coppersmith, D., and , and S. Winograd. 1987. *“Matrix multiplication via arithmetic progressions.”* *Proceedings of 19th annual ACM symposium on the theory of computing,* 1–6. New York: ACM. Dijkstra, E. W. 1959, *“A note on two problems in connexion with graphs.”* *Numerische Mathematik* Vol. 1: 269–271. Dijkstra, E. W. 1976. *A discipline of programming.* Englewood Cliffs, N.J.: Prentice-Hall. Fine, T. L. 1973. *Theories of probability.* New York: Academic Press. Fischer, M. J., and , and M. O. Rabin. 1974. *“"Super-exponential complexity of Presburger Arithmetic."”* *In Complexity of computation,* R. M. Karp, ed., , ed 27–41. Providence, R.I.: American Mathematical Society. Floyd, R. W. 1962. *“Algorithm 97: Shortest path.”* *Communications of the ACM* Vol. 5, no. 6: 345. Fredman, M.L., and , and R. E. Tarjan. 1987. *“Fibonacci heaps and their uses in improved network optimization problems.”* *Journal of the ACM* Vol. 34, no. 3: 596–615. Fussenegger, F., and , and H. Gabow. 1976. *“Using comparison trees to derive lower bounds for selection problems.”* *Proceedings of 17th annual IEEE symposium on the foundations of computer science,* 178–182. Long Beach, Cal.: IEEE Computer Society. Garey, M. R., and , and D. S. Johnson. 1979. *Computers and intractability.* New York: W. H. Freeman. Gilbert, E. N., and , and E. F. Moore. 1959. *“Variable length encodings.”* *Bell System Technical Journal* Vol. 38, no. 4: 933–968. Godbole, S. 1973. *“On efficient computation of matrix chain products.”* *IEEE Transactions on Computers C-22,* Vol. no. 9: 864–866. Graham, R. L., , D. E. Knuth, and , and O. Patashnik. 1989. *Concrete mathematics.* Reading, Mass.: Addision-Wesley. Graham, R. L., and , and P. Hell. 1985. *“On the history of the minimum spanning tree problem.”* *Annals of the History of Computing* Vol. 7, no. 1: 43–57. Gries, D. 1981. *The science of programming.* New York: Springer-Verlag. Grzegorczyk, A. 1953. *“Some classes of recursive functions.”* *Rosprawy Matematyzne 4.* Mathematical Institute of the Polish Academy of Sciences. Hardy, G. H., and , and E. M. Wright. 1960. *The theory of numbers.* New York: Oxford University Press. Hartmanis, J., and , and R. E. Stearns. 1965. *“On the computational complexity of algorithms.”* *Transactions of the American Mathematical Society* Vol. 117: 285–306. Hoare, C. A. R. 1962. *“Quicksort.”* *Computer Journal 5,* Vol. no. 1: 10–15. Hopcroft, J. E., and , and J. D. Ullman. 1979. *Introduction to automata theory, languages, and computation.* Reading, Mass.: Addison-Wesley. Horowitz, E., and , and S. Sahni. 1974. *“Computing partitions with applications to the knapsack problem.”* *Journal of the ACM* Vol. 21: 277–292. Horowitz, E., and , and S. Sahni. 1978. *Fundamentals of computer algorithms.* Woodland Hills, Cal.: Computer Science Press. Hu, T. C., and , and M. R. Shing. 1982. *“Computations of matrix chain products, Part 1.”* *SIAM Journal on Computing 11,* Vol. no. 2: 362–373. Hu, T. C., and , and M. R. Shing. 1984. *“Computations of matrix chain products, Part 2.”* *SIAM Journal on Computing 13,* Vol. no. 2: 228–251. Huang, B. C., and , and M. A. Langston. 1988. *“Practical in-place merging.”* *Communications of the ACM* Vol. 31: 348–352. Hyafil, L. 1976. *“Bounds for selection.”* *SIAM Journal on Computing 5,* Vol. no. 1: 109–114. Iverson, G. R., , W. H. Longcor, , F. Mosteller, , J. P. Gilbert, and , and C. Youtz. 1971. *“Bias and runs in dice throwing and recording: A few million throws.”* *Psychometrika* Vol. 36: 1–19. Jacobson, N. 1951. *Lectures in abstract algebra.* New York: D. Van Nostrand Company. Jarník, V. 1930. 0 jistém problému minimálnim. Praca Moravské Prirodovedecké Spolecnosti Vol. 6: 57–63. Johnson, D. B. 1977. *“Efficient algorithms for shortest paths in sparse networks.”* *Journal of the ACM 24,* Vol. no. 1: 1–13. Keynes, J. M. 1948. *A treatise on probability.* London: Macmillan. (Originally published in 1921.) Kingston, J. H. 1990. *Algorithms and data structures: Design, correctness, and analysis.* Reading, Mass.: Addison-Wesley. Knuth, D. E. 1998. *The art of computer programming, vol. II: Seminumerical algorithms.* Reading, Mass.: Addison-Wesley. Knuth, D. E. 1973. *The art of programming, Volume III: Sorting and searching.* Reading, Mass.: Addison-Wesley. Knuth, D. E. 1976. *“Big omicron and big omega and big theta.”* *SIGACT News 8,* Vol. no. 2: 18–24. Kruse, R. L. 1994. *Data structures and program design.* Englewood Cliffs, N.J.: Prentice Hall. Kruskal, J. B., Jr. 1956. *“On the shortest spanning subtree of a graph and the traveling salesman problem.”* *Proceedings of the American Mathematical Society 7,* Vol. no. 1: 48–50. Kumar, V.,, A. Grama, , A. Gupta, and , and G. Karypis. 1994. *Introduction to parallel computing.* Redwood City, Cal.: Benjamin Cummings. Ladner, R. E. 1975. *“On the structure of polynomial time reducibility.”* *Journal of the ACM* Vol. 22: 155–171. van Lambalgen, M. 1987. *Random sequences. Ph.D. diss.,* University of Amsterdam. Lawler, E. L. 1976. *Combinatorial optimization: Networks and matroids.* New York: Holt, Rinehart and Winston. Levin, L. A. 1973. *“Universal sorting problems.”* *Problemy Peredaci, Informacii* Vol. 9: 115–116 (in Russian). English translation in *Problems of Information Transmission* Vol. 9: 265–266. von Mises, R. 1919. *“Grundlagen der Wahrscheinlichkeitsrechnung.”* *Mathematische Zeitschrft* Vol. 5: 52–99. von Mises, R. 1957. *Probability, statistics, and truth.* London: George, Allen & Unwin. (Originally published in Vienna in 1928.) Neapolitan, R. E. 1990. *Probabilistic reasoning in expert systems.* New York: Wiley. Neapolitan, R. E. 1992. *“A limiting frequency approach to probability based on the weak law of large numbers.”* *Philosophy of Science 59,* Vol. no. 3: 389–407. Neapolitan, R. E. 2003. *Learning Bayesian Networks.* Prentice Hall. Papadimitriou, C. H. 1994. *Computational complexity.* Reading, Mass.: Addison-Wesley. Pearl, J. 1986. *“Fusion, propagation, and structuring in belief networks.”* *Artificial Intelligence 29,* Vol. no. 3: 241–288. Pearl, J. 1988. *Probabilistic reasoning in intelligent systems.* San Mateo, Cal.: Morgan Kaufmann. Pratt, V. 1975. *“Every prime number has a succinct certificate.”* *SIAM Journal on Computing 4,* Vol. no. 3: 214–220. Prim, R. C. 1957. *“Shortest connection networks and some generalizations.”* *Bell System Technical Journal* Vol. 36: 1389–1401. Rabin, MO. 1980. *“Probabilistic algorithms for primality testing.”* *Journal of Number Theory* Vol. 12: 128–138. Sahni, S. 1988. *Concepts in discrete mathematics.* North Oaks, Minn.: The Camelot Publishing Company. Schonhage, A., , M. Paterson, and , and N. Pippenger. 1976. *“Finding the median.”* *Journal of Computer and System Sciences 13,* Vol. no. 2: 184–199. Strassen, V. 1969. *“Gaussian elimination is not optimal.”* *Numerische Mathematik* Vol. 13: 354–356. Tarjan, R. E. 1983. *Data structures and network algorithms,* Philadelphia: SIAM. Turing, A. 1936. *“On computable numbers, with an application to the Entscheidungsproblem.”* *Proceeding of the London Mathematical Society 2,* Vol. no. 42: 230–265. Turing, A. 1937. *“On computable numbers, with an application to the Entscheidungsproblem.”* *Proceedings of the London Mathematical Society 2,* Vol. no. 43: 544–546. Yao, A. C. 1975. *“An O(|E|log log|V|) algorithm for finding minimum spanning trees.”* *Information Processing Letters 4,* Vol. no. 1: 21–23. Yao, F. 1982. *“Speed-up in dynamic programming.”* *SIAM Journal on Algebraic and Discrete Methods 3,* Vol. no. 4: 532–540.