This special issue is devoted to the A¨erage-Case Analysis of Algorithms. Analysis of algorithms aims at a precise prediction of the expected performances of algorithms and data structures of general use in computer science. Quantification of performance goes from mean value estimates of costs to analysis of the probability distributions involved, under natural randomness models of the data.
The area of analysis of algorithms was initiated by D. E. Knuth almost 30 years ago in his series of books, The Art of Computer Programming, and the field is currently undergoing tangible changes. We see now the emergence of combinatorial and asymptotic methods that permit us to classify data structures into broad categories that are susceptible to a unified treatment. Probabilistic methods that have been so successful in the study of random graphs and hard combinatorial optimization problems also play an important role in the field. These developments have two important consequences for the analysis of algorithms: it becomes possible to predict average-case behavior under more general probabilistic models; at the same time it becomes possible to analyze much more structurally complex algorithms.
In July 1993, the first seminar entirely devoted to analysis of algorithms took place in Dagstuhl, Germany. On that occasion a special issue of Theoretical Ε½ . Computer Science Vol. 144, No. 1α2, 1995 was prepared. In 1995 a second seminar on AΒ¨erage-Case Analysis of Algorithms was held again in Dagstuhl. Our special Ε½ issue is an outcome of this seminar about two-thirds of the papers in this issue . originate from the seminar and is at the same time an attempt to have a representative collection of relevant contemporary research in one volume.
In our call for papers we have asked for articles ''in any area of theoretical computer science that is using analytical, probabilistic or combinatorial methods.'' Our goal has been to prepare a volume containing research papers having a fair amount of generality in order to serve as an introduction and motivation for the ''average'' reader. Alan Frieze and Colin McDiarmid have kindly agreed to write an Invited Paper surveying the algorithmic theory of random graphs. All other papers are specially contributed to this issue. We have received more excellent papers than we could include in this issue, so that some of them had to be redirected to regular issues of this journal.