Probabilistic analysis of radix algorithms on Markov sources
- This thesis covers the analysis of radix sort, radix select and the path length of digital trees under a stochastic input assumption known as the Markov model. The main results are asymptotic expansions of mean and variance as well as a central limit theorem for the complexity of radix sort and the path length of tries, PATRICIA tries and digital search trees. Concerning radix select, a variety of different models for ranks are discussed including a law of large numbers for the worst case behavior, a limit theorem for the grand averages model and the first order asymptotic of the average complexity in the quantile model. Some of the results are achieved by moment transfer techniques, the limit laws are based on a novel use of the contraction method suited for systems of stochastic recurrences.
| Author: | Kevin Leckey |
|---|---|
| URN: | urn:nbn:de:hebis:30:3-377238 |
| Publisher: | Univ.-Bibliothek |
| Place of publication: | Frankfurt am Main |
| Referee: | Ralph NeiningerORCiDGND, Hsien-Kuei Hwang |
| Advisor: | Ralph Neininger |
| Document Type: | Doctoral Thesis |
| Language: | English |
| Date of Publication (online): | 2015/06/17 |
| Year of first Publication: | 2015 |
| Publishing Institution: | Universitätsbibliothek Johann Christian Senckenberg |
| Granting Institution: | Johann Wolfgang Goethe-Universität |
| Date of final exam: | 2015/06/10 |
| Release Date: | 2015/06/17 |
| Tag: | Contraction method; Digital trees; Markov model; Probabilistic analysis of algorithms; Radix sort |
| Page Number: | 138 |
| Last Page: | 126 |
| HeBIS-PPN: | 360452167 |
| Institutes: | Informatik und Mathematik / Mathematik |
| Dewey Decimal Classification: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |
| Sammlungen: | Universitätspublikationen |
| Licence (German): |  Deutsches Urheberrecht |
