============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

               Tarde Uruguaia de Combinatória
============================================================

Título:      50 years of Linear Probing Hashing
            
Palestrante: Alfredo Viola
             Universidad de la República

Hora e Data: 14h, quarta-feira, 18 de junho de 2014

Local:       Sala Multi-usos do Numec

Resumo:

Linear  probing  hashing  is  at  the core  of  Analysis  of
Algorithms  by  its  mathematical and  historical  interest.
This key role is clearly  presented in the introduction of a
wonderful survey by Flajolet  and Chassaing in 2003 oriented
to French students, that can be summarized as follows:

"Discrete   and   continuous   mathematics   willingly   and
harmoniously  encounter and  complement.  We  would  like to
illustrate  this thesis  by presenting  a  classical problem
with several  ramifications: the analysis  of linear probing
hashing.   This  example  is  typical  of  the  analysis  of
algorithms, a topic  pioneered by Knuth and which  is at the
intersection   of  computer   science,   combinatorics,  and
probability theory."

Historical and scientific motivations include

"  ... questions  asked by  Ramanujan  to Hardy  in 1913,  a
summer work  in 1962 by Knuth  that is at the  origin of the
analysis of algorithms in  computer science, the research in
combinatorics  done by  the  statistician Kreweras,  several
encounters with the  model of random graphs by  Erd\H os and
Rényi, some complex and asymptotic analysis, trees generated
by  specific Galton--Watson processes,  and, to  conclude, a
bit of processes like the ineffable Brownian motion!".

All this contributes to a

"very precise understanding of a very simple discrete random
problem".

In this  talk I  will survey the  history of  linear probing
hashing,  and present  some  new work  in progress.   Linear
probing  hashing   is  a  very  good  example   on  how  the
development of  new methodological tools during  the past 30
years at the core of  Analytic Combinatorics is a key factor
to  understand   the  mathematical  properties   of  several
important problems.   I will try to illustrate  this fact in
several parts of my talk.