Probabilistic Analysis of Data Structures
The aim of this project (which is carried out in collaboration
with the Univsity of Versailles) is to investigate the `random'
behaviour of data structures by means of probabilistic and
analytic methods. A prominent example is the quicksort algorithm, which,
during execution, constructs a binary tree. The probabilistic
analysis of this binary search tree
yields information e.g. about the expected runtime of the algorithm.
We therefore put emphasis on binary search trees. Another topic of
investigation is the analysis of data banks via urn models. The mathematical
methods employed here include complex analysis and convergence
theorems for martingales and stochastic processes.
Selected Publications:

M. Drmota.
An analytic approach to the height of binary
search trees ii.
J. ACM 50/3 (2003), 333374.
[pdf].

M. Drmota, D. Gardy, and B. Gittenberger.
A unified presentation of some urn
models.
Algorithmica 29/12 (2001), 120147, Averagecase analysis of
algorithms (Princeton, NJ, 1998).
[MR], [pdf].

M. Drmota.
The variance of the height of binary search
trees.
Theoret. Comput. Sci. 270/12 (2002), 913919.
[MR].

M. Drmota.
The variance of the height of digital search
trees.
Acta Inform. 38/4 (2002), 261276.
[MR].

M. Drmota and D. Panario.
A rigorous proof of the Waterloo algorithm for
the discrete logarithm problem.
Des. Codes Cryptogr. 26/13 (2002), 229241, In honour of Ronald
C. Mullin.
[MR].

M. Drmota and W. Szpankowski.
Generalized Shannon code minimizes the
maximal redundancy.
In LATIN 2002: Theoretical informatics (Cancun), volume 2286 of
Lecture Notes in Comput. Sci., pages 306318. Springer, Berlin, 2002.
[MR].

M. Drmota, H. K. Hwang, and W. Szpankowski.
Precise average redundancy of an idealized
arithmetic coding.
In Data Compression Conference (Snowbirds), pages 222231, 2002.
[pdf].

M. Drmota and H. Prodinger.
The height of qbinary search trees.
Discrete Math. Theor. Comput. Sci. 5/1 (2002), 97107
(electronic).
[MR], [pdf].

M. Drmota, D. Gardy, and B. Gittenberger.
General urn models with several types
of balls and Gaussian limiting fields.
Random Structures Algorithms 24/1 (2004), 75103.
[MR], [pdf].

B. Chauvin, M. Drmota, and J. JabbourHattab.
The profile of binary search trees.
Ann. Appl. Probab. 11/4 (2001), 10421062.
[MR].

M. Drmota.
An analytic approach to the height of binary
search trees.
Algorithmica 29/12 (2001), 89119, Averagecase analysis of
algorithms (Princeton, NJ, 1998).
[MR].
