Fundamentals of the Average Case Analysis of Particular Algorithms

This book provides an introduction to the analysis of particular algorithms. lt has its origin in lecture courses given at the Universität des Saarlandes, Saarbrücken in 1980 and attheJohann Wolfgang Goethe-Universität, Frankfurt a.M. in 1982. The material can be covered in a one-semester course. ln preparing the notes for publication as a book, I have added a considerable amount of material additional to the lecture notes, with the intention of making the book more useful. My prime consideration has been to produce a textbook whose scope is selective; some of the omitted material is outlined in various exercises and should be useful in indicating possible approaches to certain problems. Moreover, problems are provided to furnish examples, to expand on the material or to indicate related results, and occasionally to guide the reader through the steps of lengthy proofs and derivations. I have referred, in various places, to those books and original papers which have been of particular assistance to me. I wish to take this opportunity to thank all those who have had apart in this work, and who have made this book possible. I am particularly indebted to Professor Dr. Günter Hotz for his encouragement in the writing of this textbook. Special thanks are due to Ute Schürfeld for careful reading of the text. Dr. P. Spuhler from Teubner­ Verlag provided co-operative and competent support in all editorial problems. Finally, I wish to thank Teubner-Verlag and John Wiley & Sons for very good and timely editorial work.

(Koprod. mit Wiley, Chichester)

1. Introduction.- 2. A Simple Class of Algorithms.- 3. Permutations and Their Applications.- 4. Random Walks, Trees, Lists.- 5. Applications.- Appendix A.- 1. Basic Definitions of Probability Theory.- 2. Grammars-Formal Power Series.- 3. Generating Functions.- 4. Linear Recurrences.- 5. Dirichlet Series.- 6. Laurent Series-Residues-Cauchy Integral Formula.- 7. Euler's Summation Formula.- Appendix B.- 1. Numbers in Combinatorial Analysis.- 2. Special Functions.- References.- Index of Notation.