Fundamentals of the average case analysis of particular algorithms.

*(English)*Zbl 0638.68026
Wiley-Teubner Series in Computer Science. Chichester etc.: John Wiley & Sons; Stuttgart: B. G. Teubner, VIII, 233 p. (1984).

The author illustrates by considering an example that the average case analysis of algorithms may require knowledge concerning the average behaviour of combinatorial objects. This is taken as a justification for an extensive study of average numbers of characteristic quantities of permutations (always under the assumption of uniform distributions). For instance, the average number of cycles, the average length of cycles, the average number of inversions is determined. This is the contents of Chapter 3.

Chapter 4 is devoted to random walks. The weight and, in particular, the cardinality of many different classes of random walks are computed. Close connections (one-to-one correspondences) between classes of random walks on the one hand and classes of trees or data structures like stacks, deques, lists, priority queues, symbol tables and dictionaries on the other hand are described. These correspondences make it possible to interprete enumeration results on random walks in terms of trees or data structures.

Since the enumeration results are sometimes so complicated that asymptotics are desirable, some techniques for determining asymptotics from generating functions are described. Computing these enumeration results and corresponding asymptotics requires results on special polynomials and higher transcendental functions and methods of classical analysis, in particular of the theory of functions of one complex variable. An appendix contains the definitions and basic properties of 8 diffrent types of numbers (like Bernoulli numbers), 10 different types of polynomials (like Legendre polynomials) and several higher transcendental functions.

Finally, some enumeration results on random walks are applied for analyzing the average behaviour of a few algorithms. The first three algorithms concern transforming expressions in straight line program computing these expressions (code generation in compilers). Here, the average number of variables appearing in the resulting straight line program is determined which is the same as the space complexity of the transformation algorithm. Then time and space complexity of two algorithms recognizing the Dyck languages are analyzed, and the last example concerns sorting networks.

There exists still a rather isolated Chapter 2 on random algorithms which is never used in the remainder of the book and an introductory first chapter which does not, however, introduce to this book stressing the importance of enumeration results in combinatorics for the average case analysis of algorithms: More than halve of the book is devoted to combinatorics and 55 out of 62 exercises concern purely combinatorical topics.

The reviewer does not want to criticize the selection of the material, but the book had very much benefited by some more examples of algorithms whose analysis would make use of further enumeration results presented in the book.

There is no doubt that many well known methods of classical mathematics are profitable for the average case analysis of algorithms, and further activities in this direction are necessary. It is the merit of the book under review that this topic is brought to the attention of a broader community of readers.

Chapter 4 is devoted to random walks. The weight and, in particular, the cardinality of many different classes of random walks are computed. Close connections (one-to-one correspondences) between classes of random walks on the one hand and classes of trees or data structures like stacks, deques, lists, priority queues, symbol tables and dictionaries on the other hand are described. These correspondences make it possible to interprete enumeration results on random walks in terms of trees or data structures.

Since the enumeration results are sometimes so complicated that asymptotics are desirable, some techniques for determining asymptotics from generating functions are described. Computing these enumeration results and corresponding asymptotics requires results on special polynomials and higher transcendental functions and methods of classical analysis, in particular of the theory of functions of one complex variable. An appendix contains the definitions and basic properties of 8 diffrent types of numbers (like Bernoulli numbers), 10 different types of polynomials (like Legendre polynomials) and several higher transcendental functions.

Finally, some enumeration results on random walks are applied for analyzing the average behaviour of a few algorithms. The first three algorithms concern transforming expressions in straight line program computing these expressions (code generation in compilers). Here, the average number of variables appearing in the resulting straight line program is determined which is the same as the space complexity of the transformation algorithm. Then time and space complexity of two algorithms recognizing the Dyck languages are analyzed, and the last example concerns sorting networks.

There exists still a rather isolated Chapter 2 on random algorithms which is never used in the remainder of the book and an introductory first chapter which does not, however, introduce to this book stressing the importance of enumeration results in combinatorics for the average case analysis of algorithms: More than halve of the book is devoted to combinatorics and 55 out of 62 exercises concern purely combinatorical topics.

The reviewer does not want to criticize the selection of the material, but the book had very much benefited by some more examples of algorithms whose analysis would make use of further enumeration results presented in the book.

There is no doubt that many well known methods of classical mathematics are profitable for the average case analysis of algorithms, and further activities in this direction are necessary. It is the merit of the book under review that this topic is brought to the attention of a broader community of readers.

Reviewer: G.Wechsung

##### MSC:

68Q25 | Analysis of algorithms and problem complexity |

05-04 | Software, source code, etc. for problems pertaining to combinatorics |

03D15 | Complexity of computation (including implicit computational complexity) |

05A15 | Exact enumeration problems, generating functions |

03-04 | Software, source code, etc. for problems pertaining to mathematical logic and foundations |

60G50 | Sums of independent random variables; random walks |