Abstract
This paper analyses the average behaviour of algorithms that operate on dynamically varying data structures subject to insertions I, deletions D, positive (resp. negative) queries Q+ (resp.Q−) under the following assumptions: if the size of the data structure is k (k ε N), then the number of possibilities for the operations D and Q+ is a linear function of k, whereas the number of possibilities for the i-th insertion or negative query is equal to i. This statistical model was introduced by J.Françon (6), (7) and D.E.Knuth(11) and differes from the model used in previous analyses (2), (3), (4), (5), (6), (7). Integrated costs for these dynamic structures are defined as averages of costs taken over the set of all their possible histories (i.e. evolutions considered up to order isomorphism) of length n. We show that the costs can be calculated for the data structures serving as implementations of linear lists, priority queues and dictionaries. The problem of finding the limiting distributions is also considered and the linear list case is treated in detail. The method uses continued fractions and orthogonal polynomials but in a paper in preparation, we show that the same results can be recovered with the help of a probabilistic model.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
L.Cheno Profils limites d'histoires sur les dictionnaires et les files de priorité. Application aux files binomiales. Thèse de 3è cycle, Université d'Orsay, 1981.
L.Cheno, P.Flajolet, J.Françon, C.Puech, J.Vuillemin Finite files, limiting profiles and variance analysis. Proceedings 18th Allerton Conf. on Com. Control and Computing (Illinois 1980).
P. Flajolet, J. Françon, J. Vuillemin Sequence of operations analysis for dynamic data structures. J. of algorithms 1, 111–141, 1980.
P. Flajolet, C. Puech, J. Vuillemin The analysis of simple lists structures. Inf. Sc. 38, 121–146, 1986.
P.Flajolet Analyse d'algorithmes de manipulation d'arbres et de fichiers. B.U.R.O. cahier 34–35, 1981.
J.Françon Combinatoire des structures de données. Thèse de doc. d'Etat. Université de Strasbourg, 1979
J. Françon Histoires de fichiers. RAIRO Inf. Th. 12, 49–62, 1978.
J.Françon, B.Randrianarimanana, R.Schott Analysis of dynamic data structures in D.E.Knuth's model. Rapport C.R.I.N. 1986.(submitted)
A. Jonassen, D.E. Knuth A trivial algorithm whose analysis isn't. J. of Comp. and System Sc. 16, 301–332, 1978.
G.D.Knott Deletion in binary storage trees. Report Stan-CS, 75–491, may 1975.
D.E.Knuth Deletions that preserve randomness. Trans. Software Eng, 351–359, 1977.
D.E.Knuth The art of computer programming: Sorting and Searching, vol.3, second printing, 1975.
G. Louchard Random walks, Gaussian processes and list structures. Th. Comp. Sc. 53, 99–124, 1987.
B.Randrianarimanana Analyse des structures de données dynamiques dans le modèle de D.E.Knuth. Thèse de 3ème cycle, Université Nancy 1, 1986.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1988 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Françon, J., Randrianarimanana, B., Schott, R. (1988). Analysis of dynamic algorithms in D.E.Knuth's model. In: Dauchet, M., Nivat, M. (eds) CAAP '88. CAAP 1988. Lecture Notes in Computer Science, vol 299. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0026097
Download citation
DOI: https://doi.org/10.1007/BFb0026097
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-19021-9
Online ISBN: 978-3-540-38930-9
eBook Packages: Springer Book Archive