Average Case Analysis of Algorithms on Sequences

Foreword.

Preface.

Acknowledgments.

PROBLEMS ON WORDS.

Data Structures and Algorithms on Words.

Probabilistic and Analytical Models.

PROBABILISTIC AND COMBINATORIAL TECHNIQUES.

Inclusion-Exclusion Principle.

The First and Second Moment Methods.

Subadditive Ergodic Theorem and Large Deviations.

Elements of Information Theory.

ANALYTIC TECHNIQUES.

Generating Functions.

Complex Asymptotic Methods.

Mellin Transform and Its Applications.

Analytic Poissonization and Depoissonization.

Bibliography.

Index.