On the median-of- version of Hoare’s selection algorithm
On the median-of-k version of Hoare's selection algorithm
In Hoare's (1961) original version of the algorithm the partitioning element in the central divide-and-conquer step is chosen uniformly at random from the set in question. Here we consider a variant where this element is the median of a sample of size from . We investigate convergence in distribution of the number of comparisons required and obtain a simple explicit result for the limiting average performance of the median-of-three version.
On the number of iterations required by Von Neumann addition
We investigate the number of iterations needed by an addition algorithm due to Burks et al. if the input is random. Several authors have obtained results on the average case behaviour, mainly using analytic techniques based on generating functions. Here we take a more probabilistic view which leads to a limit theorem for the distribution of the random number of steps required by the algorithm and also helps to explain the limiting logarithmic periodicity as a simple discretization phenomenon.
Leader election: a Markov chain approach
A well-studied randomized election algorithm proceeds as follows: In each round the remaining candidates each toss a coin and leave the competition if they obtain heads. Of interest is the number of rounds required and the number of winners, both related to maxima of geometric random samples, as well as the number of remaining participants as a function of the number of rounds. We introduce two related Markov chains and use ideas and methods from discrete potential theory to analyse the respective...
On the number of iterations required by Von Neumann addition
We investigate the number of iterations needed by an addition algorithm due to Burks if the input is random. Several authors have obtained results on the average case behaviour, mainly using analytic techniques based on generating functions. Here we take a more probabilistic view which leads to a limit theorem for the distribution of the random number of steps required by the algorithm and also helps to explain the limiting logarithmic periodicity as a simple discretization phenomenon.
Page 1