Speaker: Michael Fuchs and Chung-Kuei Lee, NCTU, Hsinchu/Taiwan
Title: A new approach to the analysis of random digital search trees and applications

Digital search trees are fundamental data structures in computer science. Consequently, their probabilistic analysis has attracted a lot of attention over the
last three decades. While the analysis of the mean of shape parameters is by now standard, analyzing the variance has turned out be very challenging and previous
analyses were long and messy. In a joint paper with H.-K. Hwang (Academia Sinica, Taipei) and V. Zacharovas (Vilnius University, Vilnius), we introduced a new
approach which simplifies the analysis and gives much simpler expressions for involved constants and periodic funtions. In this talk, we will give a brief
introduction into this method. Moreover, we will demonstrate the usefuleness of the method by applying it to the analysis of various shape parameters in digital
search trees as well as related algorithms, e.g., approximate counting.