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:

  1. M. Drmota. An analytic approach to the height of binary search trees ii. J. ACM 50/3 (2003), 333-374. [pdf].
  2. M. Drmota, D. Gardy, and B. Gittenberger. A unified presentation of some urn models. Algorithmica 29/1-2 (2001), 120-147, Average-case analysis of algorithms (Princeton, NJ, 1998). [MR], [pdf].
  3. M. Drmota. The variance of the height of binary search trees. Theoret. Comput. Sci. 270/1-2 (2002), 913-919. [MR].
  4. M. Drmota. The variance of the height of digital search trees. Acta Inform. 38/4 (2002), 261-276. [MR].
  5. M. Drmota and D. Panario. A rigorous proof of the Waterloo algorithm for the discrete logarithm problem. Des. Codes Cryptogr. 26/1-3 (2002), 229-241, In honour of Ronald C. Mullin. [MR].
  6. 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 306-318. Springer, Berlin, 2002. [MR].
  7. M. Drmota, H. K. Hwang, and W. Szpankowski. Precise average redundancy of an idealized arithmetic coding. In Data Compression Conference (Snowbirds), pages 222-231, 2002. [pdf].
  8. M. Drmota and H. Prodinger. The height of q-binary search trees. Discrete Math. Theor. Comput. Sci. 5/1 (2002), 97-107 (electronic). [MR], [pdf].
  9. 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), 75-103. [MR], [pdf].
  10. B. Chauvin, M. Drmota, and J. Jabbour-Hattab. The profile of binary search trees. Ann. Appl. Probab. 11/4 (2001), 1042-1062. [MR].
  11. M. Drmota. An analytic approach to the height of binary search trees. Algorithmica 29/1-2 (2001), 89-119, Average-case analysis of algorithms (Princeton, NJ, 1998). [MR].