Renewal theory in analysis of tries and strings: Extended abstract

DMTCS Proceedings, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)

Renewal theory in analysis of tries and strings: Extended abstract

Svante Janson

Abstract

We give a survey of a number of simple applications of renewal theory to problems on random strings, in particular to tries and Khodak and Tunstall codes.

Full Text: PostScript PDF