41 citations · 167 across the 47 of their papers we have counts for
6 papers · 1 filter
Partitions with Distinct Multiplicities of Parts: On An "Unsolved Problem" Posed By Herbert Wilf
James Allen Fill, Svante Janson, Mark Daniel Ward
Wilf's Sixth Unsolved Problem asks for any interesting properties of the set of partitions of integers for which the (nonzero) multiplicities of the parts are all different. We ref…
Distributional convergence for the number of symbol comparisons used by QuickSort
James Allen Fill
Most previous studies of the sorting algorithm QuickSort have used the number of key comparisons as a measure of the cost of executing the algorithm. Here we suppose that the n ind…
Distributional convergence for the number of symbol comparisons used by QuickSelect
James Allen Fill, Takehiko Nakama
When the search algorithm QuickSelect compares keys during its execution in order to find a key of target rank, it must operate on the keys' representations or internal structures,…
Exact L^2-distance from the limit for QuickSort key comparisons (extended abstract)
Patrick Bindjeme, James Allen Fill
Using a recursive approach, we obtain a simple exact expression for the L^2-distance from the limit in Régnier's (1989) classical limit theorem for the number of key comparisons re…
The limiting distribution for the number of symbol comparisons used by QuickSort is nondegenerate (extended abstract)
Patrick Bindjeme, James Allen Fill
In a continuous-time setting, Fill (2010) proved, for a large class of probabilistic sources, that the number of symbol comparisons used by QuickSort, when centered by subtracting…
Hitting times and interlacing eigenvalues: a stochastic approach using intertwinings
James Allen Fill, Vince Lyzinski
We develop a systematic matrix-analytic approach, based on intertwinings of Markov semigroups, for proving theorems about hitting-time distributions for finite-state Markov chains…