Average Case Analysis of Algorithms on Sequences

Rating:
Summary: a very good graduate-level book on analysis of algorithms
Review: If you have ever been curious to know what is the mathematics behind the fancy formulas describing the average-case behavior of algorithms -- this book is for you. An excellent addition to the classic "The Art of Computer Programming" by D.Knuth, "Introduction to Analysis of Algorithms" by R.Sedgewick and P.Flajolet, and "Analysis of Algorithms" by M.Hofri, this book walks reader through a beautiful, and at the same time very diverse (not to say complex) world of mathematic tools and techniques needed to obtain precise answers to questions like "what is the average depth of a digital tree built over $n$ strings?", or "what is the average number of comparisons performed by a Knuth-Morris-Pratt algorithm when it searches for a given pattern of length $m$ in a random text of length $n$?".

Being well organized, the book present these (sometimes very sophisticated) techniques in a simple step-by-step fashion, starting with brief reviews of several known (and necessary for future presentation) results from probability, complex analysis/special functions, and information theory. The presentation of the numerous specific techniques is split in two parts: explaining probabilistic and analytic approaches to the analysis of algorithms correspondingly. Probabilistic techniques (inequalities of moments, limit theorems, large deviations, etc.) are very useful in the analysis of complex random structures, as they often yield simple estimates of their asymptotic behavior, where more accurate techniques fail or become prohibitively laborious. Analytic techniques (generating functions, singularity analysis, saddle point techniques, Mellin transform, analytic poissonization and depoissonization) on the other hand, represent a toolbox for exact modelling of the characteristics of the algorithms, yielding estimates of unparalleled precision.

As indicated by its title, this book is mostly devoted to the analysis of a special class of combinatorial algorithms -- ones that operate with sequences of symbols, or sequences. For example, it includes a detailed analysis of various algorithms for searching and sorting alphanumeric sequences based on digital trees (tries, digital search tries, Patricia-tries, etc.), redundancy expressions for popular Lempel-Ziv data compression schemes, average complexity estimates for text pattern-matching algorithms (such as Knuth-Morris-Pratt scheme), and so on.

Following the famous tradition of "The Art of Computer Programming", the author wraps many (in some case very difficult to derive) results in the form of exercises, so that active readers can have fun solving them. As a special bonus, some of these "exercises" represent currently open research problems.

Overall, this is a very good graduate-level textbook and a valuable (and almost self-contained) source of information for everyone interested in the analysis of algorithms.