Faith E. Fich, J. Ian Munro, Patricio V. Poblete
We address the fundamental problem of permuting the elements of an array of n elements according to some given permutation. Our goal is to perform the permutation quickly using only a polylogarithmic...
Higher-Order Analysis of 2-3 Trees (1999)
We present a fourth-order fringe analysis for the expected behavior of 2-3 trees, which includes 97% of the elements in the tree. It is accomplished by exploiting the structure of the transition...
Analysis of an Adaptive Algorithm to Find the Two Nearest Neighbors (1999)
Given a set S of N distinct elements in random order and a pivot x 2 S, we study the problem of simultaneously finding the left and the right neighbors of x, i.e. L = maxfuju ! xg and R = minfvjv ?...
On The Analysis Of Linear Probing Hashing (1997)
Philippe Flajolet, Patricio V. Poblete
. This paper presents moment analyses and characterizations of limit distributions for the construction cost of hash table under the linear probing strategy. Two models are considered, that of full...
A More Precise Solution to Two Problems on Tries (1997)
Gonzalo Navarro, Patricio V. Poblete
We use the Binomial Transform to address the problem of determining the average size and leaf depth of a trie. These problems lead to the need to find the poles of the function 1 1Gammap s+1 Gammaq...
Fringe techniques for binary search trees [microform] / (1985)
Thesis (Ph. D.)--University of Waterloo, 1983.