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 Universitt des Saarlandes, Saarbrcken in 1980 and attheJohann Wolfgang
Goethe-Universitt, 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. Gnter Hotz for his encouragement in the writing of this textbook. Special thanks are due to Ute Schrfeld 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.