Average case analysis of algorithms on sequences

Description

Data structures and algorithms on words -- Probabilistic and analytical models -- Inclusion-exclusion principle -- First and second moment methods -- Subadditive ergodic theorem and large deviations -- Elements of information theory -- Generating functions -- Complex asymptotic methods -- Mellin transform and its applications -- Analytic poissonization and depoissonization.;Front Matter -- 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 -- Wiley-Interscience Series in Discrete Mathematics and Optimization.