AVERAGE CASE ANALYSIS OF ALGORITHMS ON SEQUENCES

In December 1999, during my sabbatical at Stanford, I finished the first draft of the book Average Case Analysis of Algorithms on Sequences . Since then I have been revising it. I sent the final corrections on February 12, 2001, and the book will be published by Wiley in March 2001.

To order the book from Wiley CLICK HERE, to order it from Amazon.com CLICK HERE.

The chapters on this page are quite recent version of the book (May 2000). I will not update them any more. The final and authoritative version of the book is the one published by Wiley. After the book is published, I will keep an errata. Please mail comments to me .

You still can view the preliminary version of cover designed by my wife, Mariola.

Here is the final table of contents:

Part I: PROBLEMS ON WORDS

1. Data Structures and Algorithms on Words (version 12/14/99)

2. Probabilistic and Analytic Models (version 12/17/99)

Part II: PROBABILISTIC AND COMBINATORIAL TECHNIQUES

3. Inclusion-Exclusion Principle and Its Variations (version 12/21/99)

4. First and Second Moment Methods (version 05/27/00)

5. Subadditive Ergodic Theorem and Large Deviations (version 02/04/00)

6. Elements of Information Theory (version 03/26/00)

Part III: ANALYTIC TECHNIQUES

7. Generating Functions (version 01/15/00)

8. Complex Asymptotic Methods (03/01/00)

9. Mellin Transform and Its Applications (03/015/00)

10. Analytic Poissonization and Depoissonization (06/12/00)

References

BACK TO MY HOMEPAGE