..........
..........
..........
..........
This is the fourth in an ongoing series of meetings on the analysis of algorithms, which have been held in Dagstuhl, Germany, in the past and are planned for Barcelona and other locations in the future. The 1998 meeting is intended to attract more researchers from the U. S. to the field of analysis of algorithms.
Philippe Flajolet, France
Rainer Kemp, Germany
Hosam M. Mahmoud, U.S.A.
Helmut Prodinger, Austria
Robert Sedgewick, U.S.A.
Wojciech Szpankowski, U.S.A.
Probabilistic considerations on inputs and the random combinatorial structures underlying algorithmic analysis have provided an active area of modern research. One assumes some reasonable probability distribution on input instances to an algorithm as a way of understanding the inner workings of the algorithm and its "typical behavior." Experience in the field shows that it is often unwieldy to work with exact models, where on the other hand one can say something meaningful and precise on the typical "asymptotic" behavior of the algorithm, when either the underlying combinatorial structure becomes very large or when the algorithm is challenged by massive data sets. In these cases one sometimes gets simplified but exact expressions dealing with first (or higher) order expansions of averages, moments or distributions, as some parameters of the algorithmic problem grow to be very large.
The focus of this workshop is the average-case analysis of algorithms,
and its relation to the wider areas of analytic combinatorics, exact
and limiting distributions, formal techniques, probability theory,
combinatorics and computer science. We identify the following areas
as being of particular interest:
-- Properties of large randomly-formed data structures
-- Analytic tools for analysis of algorithms
-- Probabilistic methods for analysis of algorithms
-- Combinatorial methods for analysis of algorithms
-- New results concerning average-case analysis of classical or
new algorithms
-- Data compression and language-modeling methods
-- Behavior of algorithms under massive data sets
Also, following the tradition of previous seminars, we expect to organize a special issue of Algorithica to report on the results presented at the seminar.
This workshop is sponsored by DIMACS, in conjunction with the Special Year on Massive Data Sets.
6:30-8:00
Reception at Prospect Gardens
Wednesday
July 22, 1998
No afternoon talks scheduled today!
Monday
July 20, 1998
8:30-9:00
Registration
9:00-9:10
Opening remarks (DIMACS Welcome)
Robert Sedgewick
Session I
Chair: Helmut Prodinger
9:10-10:00
Visualization of the
analysis of algorithms;
Robert Sedgewick
10:15-11:05
The Airy Distribution in Analytic Combinatorics;
Philippe Flajolet
11:05-11:30
Coffee Break
Session II
Chair: Micha Hofri
11:30-11:55
Digital Sums and Diffusion on Fractals;
Peter Grabner
12:00-12:25
Analytic Approach to the
height of binary search trees;
Michael Drmota
12:25-2:00
Lunch Break
Session III
Chair: Philippe Flajolet
2:00-2:50
Transitional behavior of the
the average cost of quicksort
with median-of-(2t+1);
Hsien-Kuei Hwang
3:00-3:25
On the analysis of partial
match queries;
Conrado Martinez-Parra
3:30-3:55
Exact form for coefficients
of algebraic generating functions
Michele Soria
3:55-4:30
Coffee Break
Session IV
Chair: Francois Bergeron
4:30-4:55
Arnold Knopfmacher
A new algorithmic approach;
to Rogers-Ramanujan's identities
5:00-5:25
The chip Problem;
Edward Reingold
Tuesday
July 21, 1998
Session V
Chair: Hosam Mahmoud
9:00-9:50
Normal convergence problem?
Two moments and a recurrence may
be the clues;
Boris Pittel
10:00-10:50
Total path length of
random recursive trees ;
James Fill
10:50-11:20
Coffee Break
Session VI
Chair: Jim Fill
11:20-11:45
Ascendents and descendents in
simply generated trees;
Bernhard Gittenberger
11:50-12:15
Stochastic processes for some
occupancy urn models;
Daniele Gardy
12:15-2:00
Lunch Break
Session VII
Chair: Boris Pittel
2:00-2:50
The complete solution to the
competitive rank selection problem;
Guy Louchard
3:00-3:25
Bounded degree spanning trees
of near minimum cost;
Eric Schmutz
3:30-3:55
A new asymptotic analysis of
the Move-To-The-Front
search cost distribution;
Predrag Jelenkovic
3:55-4:30
Coffee Break
Session VIII
Chair: Uwe Rosler
4:30-4:55
On the expected depth of random circuits;
Mordecai Golin
5:00-5:25
Lexicographical generation of
a generalized Dyck language;
Jens Liebehenschel
5:30-6:00
Problem session
7:30-
Banquet at Prospect Gardens
Session IX
Chair: Guy Louchard
9:00-9:50
Analysis of algorithms
by the contraction method;
Ludger Ruschendorf
10:00-10:50
The contraction method for
divide and conquer algorithms;
Uwe Rosler
10:50-11:20
Coffee Break
Session X
Chair: Ed Coffman
11:20-11:45
Analysis for design:
Fast approximate string matching;
Ricardo Baeza-Yates
11:50-12:15 A statistical distance measure
in genetic sequences analysis;
Robert Smythe
Thursday
July 23, 1998
Session XI
Chair: Alfredo Viola
9:00-9:50
Analysis of Algorithms for
Polynomials over finite fields;
Daniel Panario
10:00-10:50
Bandwidth packing algorithms;
Ed Coffman
10:50-11:20
Coffee Break
Session XII
Chair: Conrado Martinez
11:20-11:45
On the stack size of tries;
Markus Nebel
11:50-12:15
Algorithms for graph bisection
on the planted bisection model;
Anne Condon
12:15-2:00
Lunch Break
Session XIII
Chair: Robert Smythe
2:00-2:50
Analysis of the binary
GCD algorithm;
Brigitte Vallee
3:00-3:25
A birth-death process in binary trees;
Victor Miller
3:30-3:55
Asymptotic techniques for
random algebraic structures;
Kevin Compton
3:55-4:30
Coffee Break
Session XIV
Chair: Wojciech Szpankowski
4:30-4:55
Analysis of an algorithm to
find the nearest neigbor;
Patricio Poblete
5:00-5:25
On the analysis of
linear probing hashing;
Alfredo Viola
Friday
July 24, 1998
Session XV
Chair: Patricio Poblete
9:00-9:50
Analysis of bucket sorts
Hosam Mahmoud
10:00-10:50
Towards analytic information theory:
Evaluation of entropy-like sums
via analytic depoissonization;
Wojciech Szpankowski
10:50-11:20
Coffee Break
Session XVI:
Chair: Daniel Panario
11:20-11:45
Saddle Points in Random Matrices:
Analysis of Knuth search algorithms;
Micha Hofri
11:50-12:15
A natural (q,t)-analog of
Lagrange inversion;
Francois Bergeron
12:20-12:45
A top-down approach to the
analysis of rotations in
fringe-balanced binary search trees;
Helmut Prodinger
Princeton University is located in central New Jersey approximately 50
miles southwest of New
York City and 45 miles northeast of Philadelphia.
Newark Airport is the convenient (1h15mn) but any other airport
of the New York area is OKay (JFK to Princeton is about 2h30mn),
especially if you're renting a car. Philadelphia is also close enough.
See the
Travel Information page from Princeton University for details.
Please be advised that travel grants may be supported only if you fly on a U.S. carrier. Also, keep all original receipts. Thanks.
Another thing that people sometimes do is the following. If you know that there are enough of you you can share a limoulsine perhaps for $100-$150 (five sharing a limo will be a good and comfortable bargain)
Permanent address:
Department of Statistics/Computer & Information Systems
George Washington University
Washington, DC 20052 (USA)
Home page:
http://gwis2.circ.gwu.edu/~hosam.
Hosam Mahmoud (HOSAM@gwuvm.gwu.edu) for information specific
to the Princeton meeting,
Mail
us!
Philippe Flajolet (Philippe.Flajolet@inria.fr) for these pages.
Sandy Barbu (barbu@CS.Princeton.EDU) for room sharing and
other practical advices.