TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 9728

"Average-Case"-Analysis of Algorithms

( Jul 07 – Jul 11, 1997 )

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/9728

Organizers
  • H. Mahmoud (Washington)
  • H. Prodinger (Wien)
  • P. Flajolet (Paris)
  • R. Kemp (Frankfurt am Main)




Overview

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).


Participants
  • H. Mahmoud (Washington)
  • H. Prodinger (Wien)
  • P. Flajolet (Paris)
  • R. Kemp (Frankfurt am Main)

Related Seminars
  • Dagstuhl Seminar 9238: Experimental Software Engineering Issues (1992-09-14 - 1992-09-18) (Details)
  • Dagstuhl Seminar 9527: `Average-Case'-Analysis of Algorithms (1995-07-03 - 1995-07-07) (Details)