The twenty-eight abstracts in this report illustrate the vitality of the subject. They range from methodological to applied, covering such diverse problems as string matching and computational biology, hashing, tree data structures, selection problems in statistics, data compression and information-theory, adaptive data structures and learning, real-time and systems programming, as well as relations with computer algebra.

General methodology is often approached under a perspective that combines probabilistic intuition and analytic insight, and it is discussed in several talks. Urn models underly a great many applications, like hashing, allocations, or learning (Gardy); Brownian motion can be put to good use in the analysis of tree parameters (Louchard), while many properties of random trees in discrete mathematics are unified by a general theory that is distinctively different from branching processes (Devroye). Alternating sums, present in several algorithms, can be treated systematically by complex analysis. Many saddle point computations that arise in combinatorics can be performed automatically by a computer algebra system (Salvy), though hard problems arise in asymptotic enumerations when analysing constrained set partitions (Odlyzko). The classical framework of “analytic combinatorics” is capable of characterizing limit distributions of a great many parameters of combinatorial structures (Flajolet).

Patterns in strings are of interest for information retrieval, indexing, and also computational biology. We have by now a fair understanding of pattern occurrences in random strings (Régnier). Formal languages also lead to interesting enumerative problems (Nebel), some of which are related to random generation (Liebehenschel), where a computer algebra system like Maple offers an interesting functionality. Patterns in strings are also closely related to information theory and to digital tries that we know how to analyse under a rich variety of models (Vallée). Many problems in information theory, most notably compression, can in fact be now subjected to analytic methods, resulting in the emergence of “analytic information theory” (Szpankowski).

Trees are the data structure par excellence. The combinatorial models still pose intriguing questions. Very recent solutions to the problem of the width —equivalently the queue size in a traversal— have been found (Gittenberger), while balanced trees can be analysed under this model (Kemp). The search tree model is of direct impact on data structuring. We now see that height can be attacked by analytic methods (Drmota). This model also applies to quicksort and quickselect, where multiple selection (Mahmoud),optimal sampling (Martinez), and locality of search (Prodinger) can be precisely analysed. Sorting poses problems, some similar but others quite different when one takes into account measures of presortedness (Hwang) or fast approximate sorting by networks (Sedgewick).

Hashing algorithms constitute direct access methods with a very high service rate under favorable probabilistic conditions. In critical applications (e.g., routers), it is often crucial to quantify precisely the “risk” of long delays: a definitive solution to the variance analysis of the linear probing strategy was presented for the first time at the seminar (Poblete, Viola).

Finally, several talks illustrate the diversity of topics where analysis of algorithms may be applied. Instances are computational geometry (Golin), self-organizing search (Fill), reservation policies in communication systems (Coffman), communication protocols (Jacquet), and clock synchronization in real-time systems (Schmid).