ANALYSIS of ALGORITHMS (Research)
ANALYSIS of ALGORITHMS HOME PAGE
RESEARCH in the ANALYSIS of ALGORITHMS PAGES
[ Home Page ]
[
Research |
Problems |
Bulletin board |
People |
Resources
]
Return to Analysis of Algorithms Home Page
These pages are edited by
Philippe.Flajolet@inria.fr.
They consist largely of pointers to papers available on the web.
For people who don't have a home page,
we can store files locally.
Also, we'll try to organize the material as time goes on.
In the long run, and provided there is enough activity, these pages
should be split
into several subsections,like Papers, Surveys, etc, and
we'll need volunteers for this (!?).
Research News Index
For the moment, these pages are organized by
Issue with a random periodicity,
depending on traffic and available time not eaten by Administration(!).
I suggest that brief descriptions of new papers and research announcements
be posted by their authors directly on the
Bulletin Board. I'll try to summarize here
relevant information drawn from the Bulletin Board
(at least regarding areas where I happen to have minimal competence),
as well as things that I otherwise become aware of.
- [RN-11/04] November 2004.
With items on ANALCO'05 in Vancouver (January 2005);
AofA'05 in Barcelona (June 2005);
Special Issue on Analysis of Algorithms in
Algorithmica
(deadline January 15, 2005).
- [RN-12/03] December 2003.
With items on Events of 2004, including:
ANALCO'04 at New Orleans (January 10, 2004);
the Tenth International Workshop on Analysis of Algorithms
at MSRI, Berkeley (June 14-18, 2004); the Third Colloquium on
Mathematics and Computer Science---Algorithms, Trees, Combinatorics
and Probabilities (September 13-17, 2004) in Vienna.
- [RN-06/03] June 2003.
With items on:
The San Miniato meeting on Analysis of Algorithms,
June 22-28, 2003.
An account of the main lectures by
R. Neininger, L. Devroye, B. Vallée, B. McKay, P. Flajolet,
on (resp.) the recursive method, maximal chains in hashing strategies,
the Gaussian-ness of
Euclidean algorithms, high-dimensional
saddle-point enumeration, and analytic urn models.
- [RN-08/01] August 2001.
With items on:
The Tatihou meeting on Analysis of Algorithms,
July 2-7, 2001.
An account of the main lectures by
B. Chauvin, L. Devroye, P. Flajolet, H. K. Hwang,
B. Pittel, G. Schaeffer, W. Szpankowski, A. Viola.
- [RN-08/00] August 2000.
With items on:
The Gdansk meeting on Analysis of Algorithms,
July 3-7, 2000.
An account of the main lectures by D. Aldous, M. Drmota,
P. Flajolet, S. Janson, H. Prodinger.
- [RN-06/00] June 2000.
With items on:
The Gdansk meeting on Analysis of Algorithms,
July 3-7, 2000: the official web site maintained by
Wojtek Szpankowski.
Some books available for free on the web:
AVERAGE CASE ANALYSIS OF ALGORITHMS ON STRINGS,
by Wojtek Szpankowski;
GENERATINGFUNCTIONOLOGY, by Herb Wilf,
ALGORITHMS SEMINAR 1998-1999,
edited by Bruno Salvy.
- [RN-05/99] May 1999.
With items on:
The Barcelona meeting on Analysis of Algorithms,
June, 14-18, 1999: the official web site maintained by
Conrado Martinez. Sorts of sorts.
Trees, and trees, and trees . . .
Multidimensional data.
Operating with operators. Hashing.
Combinatorial tree models. Information theory and such.
A closed world?
- [RN-11/98] November-December 1998.
With items on:
A photograph of participants of the Princeton meeting;
Papers on quadtrees, median-quicksort, the recursive/contraction
method.
A scoop on the Barcelona meeting on Analysis of Algorithms,
June, 14-18, 1999.
The lost manuscript of Greene and Knuth.
The PhD Thesis of Pascal Hennequin (complete).
- [RN-09/98] September 1998.
With items on:
Accounts of the Princeton meeting of July 1998 (Part II):
Caching; Theory and Practice; Adaptive Search.
- [RN-07/98] July 1998.
With items on:
Accounts of the Princeton meeting of July 1998 (Part I).
Approaches,
Structures,
Trees and sorts.
- [RN-05/98] May/June 1998.
With items on:
The AofA Booklet of the Princeton
Meeting on
"Average-Case Analysis
of Algorithms".
Theory and Practice: Routers, address lookup in networks, and tries.
- [RN-01/98] January 1998.
With items on:
Princeton Meeting on "Average-Case Analysis
of Algorithms".
- [RN-11/97] November 1997.
With items on:
Knuth's first analysis of an algorithm.
The Ramanujan-Knuth Q-function.
Cost distribution in linear probing hashing.
Knuth's original note in Tex.
Odlyzko's monograph on "Asymptotic enumeration methods".
- [RN-10/97] October 1997.
With items on:
Large deviations and Quicksort.
Rooted trees.
Random generation of combinatorial structures.
New books.
- [RN-09/97] September 1997.
With items on:
The binary gcd algorithm. Wobbles. Why care about wobbles?
Optimal directed trees. Local and central limit laws.
- [RN-08/97] August 1997.
With items on:
Mergesort; Gaussian Laws; Depoissonization;
Recursive algorithms, probability metrics, and contraction method.
- [RN-07/97] July 1997.
With items on:
Hashing with linear probing;
A chapter on analysis of algorithms;
A recurrence in universal coding theory;
Analytic Combinatorics;
Open problems in the analysis of sorting and searching algorithms;
Hofri's book;
The Art of Computer Programming;
Linear probing strikes again;
Gcd algorithms;
Quickselect.