The First Workshop on Analytic Algorithmics and Combinatorics (ANALCO04)


The First Workshop on Analytic Algorithmics and Combinatorics (ANALCO04) will be held in New Orleans on January 10, 2004, at the Astor Crowne Plaza Hotel.

The aim of the ANALCO workshop is to provide a forum for the presentation of original research in the analysis of algorithms and associated combinatorial structures. We invite both papers that study properties of fundamental combinatorial structures that arise in practical computational applications (such as permutations, trees, strings, tries, and graphs) and papers that address the precise analysis of algorithms for processing such structures, including: average-case analysis; analysis of moments, extrema, and distributions; and probabilistic analysis of randomized algorithms. Submissions that present significant new information about classic algorithms are welcome, as are analyses of new algorithms that present unique analytic challenges. We also invite submissions that address tools and techniques for the analysis of algorithms and combinatorial structures, both mathematical and computational.

The scientific program will include ample time for discussion and debate of topics in this area.

This workshop precedes the ACM-SIAM Symposium on Discrete Algorithms (SODA04) being held January 11-13, 2004.

The workshop will take place on the same day as the Sixth Annual Workshop on Algorithm Engineering and Experiments (ALENEX04). Since researchers in both fields are approaching the problem of learning detailed information about the performance of particular algorithms, we expect that interesting synergies will develop. The proceedings of ALENEX and ANALCO will be published as a single volume.

A paper that has been reviewed and accepted for presentation at SODA is not eligible for submission to ANALCO. We recognize, however, that some research projects spawn multiple papers that elaborate on different aspects of the work. We are willing to respond to inquiries about SODA, ALENEX, and ANALCO papers that may overlap. Inquires regarding ANALCO may be sent to workshop organizer Bob Sedgewick at

The ANALCO workshop is supported by SIAM (Society for Industrial and Applied Mathematics) and SIGACT (ACM Special Interest Group on Algorithms and Computation Theory).

Program Committee

Kevin Compton, University of Michigan
Luc Devroye, McGill University, Canada
Mordecai Golin, The Hong Kong University of Science and Technology, Hong Kong
Hsien-Kuei Hwang, Academia Sinica, Taiwan
Robert Sedgewick (chair), Princeton University
Wojciech Szpankowski, Purdue University
Brigitte Vallée, Université de Caen, France
Jeffrey S. Vitter, Purdue University

Invited Plenary Speaker

Philippe Flajolet, INRIA, France
Theory and Practice of Probabilistic Counting Algorithms


Authors are invited to submit 10-page extended abstracts by 5:00 PM EDT, September 19, 2003. To submit a paper for consideration, please e-mail a Postscript (.ps) or PDF (.pdf) version of the paper to Bob Sedgewick at

Notification of acceptance or rejection will be sent by the end of November 2003. The deadline for receipt of papers in final version will be included in the acceptance notification. Presenters must have submitted the final versions of their papers in order to be able to present them at the workshop.