Sexta-feira, 15 de outubro de 1999
Auditório Jacy Monteiro
Instituto de Matemática e Estatística, USP
3:30 - 4:20 Alfredo Viola, Universidad de la Republica, Uruguay
On Combinatorial Aspects of Linear Probing Hashing
We present moment analyses and characterizations of limit distributions for
the construction cost of hash tables under the linear probing strategy.
For full tables, the construction cost has expectation $O(n^{3/2})$, the
standard deviation is of the same order, and a limit law of the Airy type
holds. For sparse tables with a fixed filling ratio strictly smaller than 1,
the construction cost has expectation $O(n)$, standard deviation
$O(\sqrt{n})$, and a limit law of the Gaussian type.
We then give a presentation of combinatorial relations with other problems
leading to Airy phenomena (like graph connectivity, tree inversions, tree path
length, or area under excursions).
This is a joint work with Philippe Flajolet (INRIA) and Patricio Poblete
(Universidad de Chile).
Y. Kohayakawa
<yoshi@ime.usp.br>
Last modified: Fri Oct 8 11:52:01 EDT 1999