Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Analytic analysis of algorithms

  • Conference paper
  • First Online:
Automata, Languages and Programming (ICALP 1992)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 623))

Included in the following conference series:

  • 182 Accesses

Abstract

The average case analysis of algorithms can avail itself of the development of synthetic methods in combinatorial enumerations and in asymptotic analysis. Symbolic methods in combinatorial analysis permit to express directly the counting generating functions of wide classes of combinatorial structures. Asymptotic methods based on complex analysis permit to extract directly coefficients of structurally complicated generating functions without a need for explicit coefficient expansions.

Three major groups of problems relative to algebraic equations, differential equations, and iteration are presented. The range of applications includes formal languages, tree enumerations, comparison-based searching and sorting, digital structures, hashing and occupancy problems.

These analytic approaches allow an abstract discussion of asymptotic properties of combinatorial structures and schemas while opening the way for automatic analysis of whole classes of combinatorial algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Albert, L., Casas, R., Fages, F., Torrecillas, A., and Zimmermann, P. Average case analysis of unification algorithms. In Proceedings of STACS'91 (1991), C. Choffrut and M. Jantzen, Eds., Lecture Notes in Computer Science, pp. 196–213.

    Google Scholar 

  2. Albert, L., and Fages, F. Average case analysis of the Rete pattern-matching algorithm. In Automata, Languages and Programming (1988), T. Lepistö and A. Salomaa, Eds., vol. 317 of Lecture Notes in Computer Science, Springer Verlag. Proceedings of 15th ICALP Colloquium, Tempere, Finland, July 1938.

    Google Scholar 

  3. Aldous, D., and Shields, P. A diffusion limit for a class of randomly growing binary trees. Probability Theory and Related Fields 79, 4 (1988), 509–542.

    Article  Google Scholar 

  4. Bender, E. A. Central and local limit theorems applied to asymptotic enumeration. Journal of Combinatorial Theory 15 (1973), 91–111.

    Article  Google Scholar 

  5. Bender, E. A. Asymptotic methods in enumeration. SIAM Review 16, 4 (Oct. 1974), 485–515.

    Article  Google Scholar 

  6. Bender, E. A., and Richmond, L. B. Central and local limit theorems applied to asymptotic enumeration II: Multivariate generating functions. Journal of Combinatorial Theory, Series A 34 (1983), 255–265.

    Article  Google Scholar 

  7. Berstel, J., and Reutenauer, C.Les séries rationnelles et leurs langages. Masson, Paris, 1984.

    Google Scholar 

  8. Canfield, E. R. Central and local limit theorems for the coefficients of polynomials of binomial type. Journal of Combinatorial Theory, Series A 23 (1977), 275–290.

    Article  Google Scholar 

  9. Casas, R., Diaz, J., and Martinez, C. Statistics on random trees. In Automata, Languages, and Programming (1991), J. Leach Albert et al., Ed., vol. 510 of Lecture Notes in Computer Science, pp. 186–203, Proceedings of the 18th ICALP Conference, Madrid, July 1991.

    Google Scholar 

  10. Casas, R., Fernández Camacho, M.-I., and Steyaert, J.-M. Algebraic simplification in computer algebra: An analysis of bottom-up algorithms. Theoretical Computer Science 74 74 (1990), 273–298.

    Article  Google Scholar 

  11. Choppy, C., Kaplan, S., and Soria, M. Complexity analysis of term rewriting systems. Theoretical Computer Science 67 (1989), 261–282.

    Article  Google Scholar 

  12. Compton, K. J. A logical approach to asymptotic combinatorics. I. First order properties. Advances in Mathematics 65 (1987), 65–96.

    Article  Google Scholar 

  13. Compton, K. J. A logical approach to asymptotic combinatorics. II. Second-order properties. Journal of Combinatorial Theory, Series A 50 (1987), 110–131.

    Article  Google Scholar 

  14. Compton, K. J. 0−1 laws in logic and combinatorics. In Proceedings NATO Advanced Study Institute on Algorithms and Order (Dordrecht, 1988), I. Rival, Ed., Reidel, pp. 353–383.

    Google Scholar 

  15. Comtet, L.Advanced Combinatorics. Reidel, Dordrecht, 1974.

    Google Scholar 

  16. De Bruijn, N. G. Asymptotic Methods in Analysis. Dover, 1981. A reprint of the third North Holland edition, 1970 (first edition, 1958).

    Google Scholar 

  17. De Bruijn, N. G., Knuth, D. E., and Rice, S. O. The average height of planted plane trees. In Graph Theory and Computing (1972), R. C. Read, Ed., Academic Press, pp. 15–22.

    Google Scholar 

  18. Devroye, L. Branching processes in the analysis of the heights of trees. Acta Informatica 24 (1987), 277–298.

    Article  Google Scholar 

  19. Dienes, P.The Taylor Series. Dover, New York, 1958. A reprint of the first Oxford University Press edition, 1931.

    Google Scholar 

  20. Fagin, R., Nievergelt, J., Pippenger, N., and Strong, R. Extendible hashing: A fast access method for dynamic files. A.C.M. Trans. Database Syst. 4 (1979), 315–344.

    Article  Google Scholar 

  21. Fayolle, G., Flajolet, P., and Hofri, M. On a functional equation arising in the analysis of a protocol for a multiaccess broadcast channel. Advances in Applied Probability 18 (1986), 441–472.

    Google Scholar 

  22. Flajolet, P.Analyse d'algorithmes de manipulation d'arbres et de fichiers, vol. 34–35 of Cahiers du Bureau Universitaire de Recherche Opérationnelle. Université Pierre et Marie Curie, Paris, 1981. 209 pages.

    Google Scholar 

  23. Flajolet, P. Analytic models and ambiguity of context-free languages. Theoretical Computer Science 49 (1987), 283–309.

    Article  Google Scholar 

  24. Flajolet, P. Mathematical methods in the analysis of algorithms and data structures. In Trends in Theoretical Computer Science, E. Börger, Ed. Computer Science Press, Rockville, Maryland, 1988, ch. 6, pp. 225–304. (Lecture Notes for A Graduate Course in Computation Theory, Udine, 1984).

    Google Scholar 

  25. Flajolet, P., and Golin, M. Mellin transforms and asymptotics: The mergesort recurrence. Report, Institut National de Recherche en Informatique et en Automatique, January 1992. 11 pages.

    Google Scholar 

  26. Flajolet, P., Gonnet, G., Puech, C., and Robson, J. M. The analysis of multidimensional searching in quad-trees. In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms (Philadelphia, 1991), SIAM Press, pp. 100–109.

    Google Scholar 

  27. Flajolet, P., and Martin, G. N. Probabilistic counting algorithms for data base applications. J. Comput. Syst. Sci. 31, 2 (Oct. 1985), 182–209.

    Article  Google Scholar 

  28. Flajolet, P., and Odlyzko, A. M. Random mapping statistics. In Advances in Cryptology (1990), J.-J. Quisquater and J. Vandewalle, Eds., vol. 434 of Lecture Notes in Computer Science, Springer Verlag, pp. 329–354. Proceedings of Eurocrypt'89, Houtalen, Belgium, April 1989.

    Google Scholar 

  29. Flajolet, P., and Odlyzko, A. M. Singularity analysis of generating functions. SIAM Journal on Discrete Mathematics 3, 2 (1990), 216–240.

    Article  Google Scholar 

  30. Flajolet, P., and Puech, C. Partial match retrieval of multidimensional data. Journal of the ACM 33, 2 (1986), 371–407.

    Article  Google Scholar 

  31. Flajolet, P., and Richmond, B. Generalized digital trees and their difference-differential equations, Apr. 1991. 15 pages. INRIA Research Report 1423. To appear in Random Structures and Algorithms.

    Google Scholar 

  32. Flajolet, P., Salvy, B., and Zimmermann, P. Automatic average-case analysis of algorithms. Theoretical Computer Science, Series A 79, 1 (February 1991), 37–109.

    Google Scholar 

  33. Flajolet, P., and Sedgewick, R. Digital search trees revisited. SIAM Journal on Computing 15, 3 (Aug. 1986), 748–767.

    Article  Google Scholar 

  34. Flajolet, P., Sipala, P., and Steyaert, J.-M. Analytic variations on the common subexpression problem. In Automata, Languages, and Programming (1990), M. S. Paterson, Ed., vol. 443 of Lecture Notes in Computer Science, pp. 220–234. Proceedings of the 17th ICALP Conference, Warwick, July 1990.

    Google Scholar 

  35. Flajolet, P., and Soria, M. Gaussian limiting distributions for the number of components in combinatorial structures. Journal of Combinatorial Theory, Series A 53 (1990), 165–182.

    Article  Google Scholar 

  36. Flajolet, P., and Steyaert, J.-M. A complexity calculus for classes of recursive search programs over tree structures. In Proceedings of the 22nd Annual Symposium on Foundations of Computer Science (1981), IEEE Computer Society Press, pp. 386–393.

    Google Scholar 

  37. Flajolet, P., and Steyaert, J.-M. A complexity calculus for recursive tree algorithms. Mathematical Systems Theory 19 (1987), 301–331.

    Article  Google Scholar 

  38. Gamkrelidze, R. V., Ed. Analysis I, Integral Representations and Asymptotic Methods, vol. 13 of Encyclopedia of Mathematical Sciences. Springer Verlag, 1989.

    Google Scholar 

  39. Gardy, D. Bases de données et allocations aléatoires: Quelques analyses de performance Doctorate in sciences, Université de Paris-Sud, 1989.

    Google Scholar 

  40. Gardy, D. Méthode de col et lois limites en analyse combinatoire. Theoretical Computer Science 92, 2 (1992), 261–280.

    Article  Google Scholar 

  41. Gessel, I. M. Symmetric functions and P-recursiveness. Journal of Combinatorial Theory, Series A 53 (1990), 257–285.

    Article  Google Scholar 

  42. Gessel, I. M., and Stanley, R. P. Algebraic enumeration. Preprint, 1989. To appear as a chapter in the Handbook of Combinatorics, R. Graham, M. Grötschel and L. Lovász, Eds.

    Google Scholar 

  43. Goulden, I. P., and Jackson, D. M.Combinatorial Enumeration. John Wiley, New York, 1983.

    Google Scholar 

  44. Graham, R., Knuth, D., and Patashnik, O. Concrete Mathematics Addison Wesley, 1989.

    Google Scholar 

  45. Greene, D. H. Labelled formal languages and their uses. PhD thesis, Stanford University, June 1983.

    Google Scholar 

  46. Greene, D. H., and Knuth, D. E.Mathematics for the analysis of algorithms. Birkhauser, Boston, 1981.

    Google Scholar 

  47. Harary, F., and Palmer, E. M. Graphical Enumeration. Academic Press, 1973.

    Google Scholar 

  48. Henrici, P.Applied and Computational Complex Analysis. John Wiley, New York, 1977. 3 volumes.

    Google Scholar 

  49. Hoshi, M., and Flajolet, P. Page usage in quadtree indexes. Report 1434, Institut National de Recherche en Informatique et en Automatique, May 1991. 19 pages. Accepted for publication in BIT.

    Google Scholar 

  50. Joyal, A. Une théorie combinatoire des séries formelles. Advances in Mathematics 42, 1 (1981), 1–82.

    Article  Google Scholar 

  51. Kemp, R.Fundamentals of the Average Case Analysis of Particular Algorithms. Wiley-Teubner, Stuttgart, 1984.

    Google Scholar 

  52. Kirschenhofer, P., and Prodinger, H. On some applications of formulæ of Ramanujan in the analysis of algorithms. Mathematika 38 (1991), 14–33.

    Google Scholar 

  53. Kirschenhofer, P., Prodinger, H., and Szpankowski, W. On the variance of the external path length in a symmetric digital trie. Discrete Applied Mathematics 25 (1989), 129–143.

    Article  Google Scholar 

  54. Knuth, D. E. The Art of Computer Programming, vol. 1: Fundamental Algorithms. Addison-Wesley, 1968. Second edition, 1973.

    Google Scholar 

  55. Knuth, D. E. The Art of Computer Programming, vol. 3: Sorting and Searching. Addison-Wesley, 1973.

    Google Scholar 

  56. Knuth, D. E. The average time for carry propagation. Indagationes Mathematicae 40 (1978), 238–242.

    Google Scholar 

  57. Knuth, D. E., and Schönhage, A. The expected linearity of a simple equivalence algorithm. Theoretical Computer Science 6 (1978), 281–315.

    Article  Google Scholar 

  58. Lifschitz, V., and Pittel, B. The number of increasing subsequences of the random permutation. Journal of Combinatorial Theory, Series A 31 (1981), 1–20.

    Article  Google Scholar 

  59. Lipshitz, L. The diagonal of a D-finite power series is D-finite. J. Algebra 113 (1988), 373–378.

    Article  Google Scholar 

  60. Lipshitz, L.D-finite power series. J. Algebra 122 (1989), 353–373.

    Article  Google Scholar 

  61. Louchard, G. The Brownian motion: a neglected tool for the complexity analysis of sorted table manipulation. RAIRO Theoretical Informatics 17 (1983).

    Google Scholar 

  62. Massazza, P. Holonomic functions and their relation to linearly constrained languages. Manuscript, 1991. 14 pages. Based on the authors's Ph. D. Thesis, University of Milan, 1991.

    Google Scholar 

  63. McKay, B. D. The asymptotic numbers of regular tournaments, eulerian digraphs and eulerian oriented graphs. Comhinatorica 10, 4 (1990), 367–377.

    Google Scholar 

  64. Meir, A., and Moon, J. W. On the altitude of nodes in random trees. Canadian Journal of Mathematics 30 (1978), 997–1015.

    Google Scholar 

  65. Odlyzko, A. M. Enumeration of strings. In Combinatorial Algorithms on Words (1985), A. Apostolico and Z. Galil, Eds., vol. 12 of NATO Advance Science Institute Series. Series F: Computer and Systems Sciences, Springer Verlag, pp. 205–228.

    Google Scholar 

  66. Odlyzko, A. M. Asymptotic enumeration methods. Preprint, Mar. 1992. To appear as a chapter in the Handbook of Combinatorics,R. Graham, M. Grötschel and L. Lovász, Ed.

    Google Scholar 

  67. Odlyzko, A. M., and Richmond, L. B. Asymptotic expansions for the coefficients of analytic generating functions. Aequationes Mathematicae 28 (1985), 50–63.

    Google Scholar 

  68. Pólya, G., and Read, R. C.Combinatorial Enumeration of Groups, Graphs and Chemical Compounds. Springer Verlag, New York, 1987.

    Google Scholar 

  69. Salvy, B. Asymptotique automatique et fonctions génératrices. Ph. D. thesis, École Polytechnique, 1991.

    Google Scholar 

  70. Sedgewick, R.Algorithms, second ed. Addison-Wesley, Reading, Mass., 1988.

    Google Scholar 

  71. Soria-Cousineau, M.Méthodes d'analyse pour les constructions combinatoires et les algorithmes. Doctorat d'état, Université de Paris-Sud, Orsay, July 1990.

    Google Scholar 

  72. Stanley, R. P. Generating functions. In Studies in Combinatorics, M.A.A. Studies in Mathematics, Vol. 17. (1978), G.-C. Rota, Ed., The Mathematical Association of America, pp. 100–141.

    Google Scholar 

  73. Stanley, R. P. Differentiably finite power series. European Journal of Combinatorics 1 (1980), 175–188.

    Google Scholar 

  74. Stanley, R. P. Enumerative Combinatorics, vol. I. Wadsworth & Brooks/Cole, 1986.

    Google Scholar 

  75. Steyaert, J.-M. Structure et complexité des algorithmes. Doctorat d'état, Université Paris VII, Apr. 1984.

    Google Scholar 

  76. Steyaert, J.-M., and Flajolet, P. Patterns and pattern-matching in trees: an analysis. Information and Control 58, 1–3 (July 1983), 19–58.

    Article  Google Scholar 

  77. Szpankowski, W. Patricia tries again revisited. Journal of the ACM 37, 4 (1990), 691–711.

    Article  Google Scholar 

  78. Titchmarsh, E. C. The Theory of Functions, second ed. Oxford University Press, 1939.

    Google Scholar 

  79. Vitter, J. S., and Flajolet, P. Analysis of algorithms and data structures. In Handbook of Theoretical Computer Science, J. van Leeuwen, Ed., vol. A: Algorithms and Complexity. North Holland, 1990, ch. 9, pp. 431–524.

    Google Scholar 

  80. Wasow, W. Asymptotic Expansions for Ordinary Differential Equations Dover, 1987. A reprint of the John Wiley edition, 1965.

    Google Scholar 

  81. Wilf, H. S. Generatingfunctionology. Academic Press, 1990.

    Google Scholar 

  82. Wimp, J., and Zeilberger, D. Resurrecting the asymptotics of linear recurrences. Journal of Mathematical Analysis and Applications 111 (1985), 162–176.

    Article  Google Scholar 

  83. Zeilberger, D. A holonomic approach to special functions identities. Journal of Computational and Applied Mathematics 32 (1990), 321–368.

    Article  Google Scholar 

  84. Zimmermann, P.Séries génératrices et analyse automatique d'algorithmes. Thèse de Doctorat, École Polytechnique, Palaiseau, France, 1991.

    Google Scholar 

  85. Zimmermann, P. Analysis of functions with a finite number of return values, Feb. 1992. 12 pages.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Algorithms Project, INRIA, Rocquencourt, F-78150, Le Chesnay, France

    Philippe Flajolet

Authors
  1. Philippe Flajolet
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

W. Kuich

Rights and permissions

Reprints and permissions

Copyright information

© 1992 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Flajolet, P. (1992). Analytic analysis of algorithms. In: Kuich, W. (eds) Automata, Languages and Programming. ICALP 1992. Lecture Notes in Computer Science, vol 623. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-55719-9_74

Download citation

  • DOI: https://doi.org/10.1007/3-540-55719-9_74

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-55719-7

  • Online ISBN: 978-3-540-47278-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation