Special volume on the mathematical analysis of algorithms

Click here !
Table of contents:

Mellin transforms and asymptotics: Harmonic sums Ph. Flajolet, X. Gourdon, P. Dumas 3--58
Constructible differentially finite algebraic series in several variables F. Bergeron, U. Sattler 59--65
Marking in combinatorial constructions: Generating functions and limiting distributions M. Drmota, M. Soria 67--99
Mellin transforms and asymptotics: Finite differences and Rice's integrals Ph. Flajolet, R. Sedgewick 101--124
Dynamic analysis of some relational databases parameters D. Gardy, G. Louchard 125--159
Asymptotic behavior of the Lempel--Ziv parsing scheme and digital search trees P. Jacquet, W. Szpankowski 161--197
Analysis of an optimized search algorithm for skip lists P. Kirschenhofer, C. Mart\'{\i }nez, H. Prodinger 199--220
Probabilistic analysis of bucket recursive trees H.M. Mahmoud, R.T. Smythe 221--249
On the variance of a class of inductive valuations of data structures for digital search W. Schachinger 251--275
Random trees in queueing systems with deadlines U. Schmid 277--314

Forword from H. Prodinger and W. Szpankowski

This special issue is devoted to the it Mathematical Analysis of Algorithms. This area was started by D.E. Knuth almost 30 years ago in his series of books it The Art of Computer Programming in order to understand behaviors of algorithms from a quantitative point of view (i.e., on average, in probability, etc.). Unfortunately, this area of research and scientific activity never had a "home". Only in July 1993, the first seminar entirely devoted to it took place in Dagstuhl, Germany. The next seminar will be again in 1995.
The present special issue is an attempt to have a representative collection of relevant research papers in one volume. In our Call for Papers we have asked for articles "in any area of theoretical computer science that is using analytical, probabilistic or combinatorial methods". Our goal was to prepare a volume containing research papers having a reasonable amount of generality in order to serve as an introduction and motivation for an "average" reader. We have received more excellent papers than we could include in this issue, and some of them had to be re-directed to regular issues of this journal. Philippe Flajolet has kindly agreed to write an Invited Paper surveying the applications of the Mellin transform in the analysis of algorithms. This topic was started by D.E. Knuth (inspired by N.G. de Bruijn) and proved to be extremely useful and important. Thanks to Flajolet and his coauthors this method has become an essential and widely used tool for researchers in this area. We are very grateful to M. Nivat, the Editor-in-Chief of Theoretical Computer Science for having given us the opportunity to be Guest Editors of this special issue. Thanks are also due to Philippe Flajolet for his assistance during the preparation of this issue, as well as to the contributors and the referees for their dedicated efforts. Finally, we appreciate the help we have received from the staff of Elsevier, especially Dr. J.-W.M. Kok. We hope that the readers find this issue interesting and useful in their scientific endeavors.

We dedicate this issue to D.E. Knuth, the founding father of the analytical (precise) analysis of algorithms.


Wojciech Szpankowski,

(Back to List of Papers)