Derivation of Randomized Algorithms.
Sanguthevar Rajasekaran, John H. Reif · Defense Technical Information Center (DTIC) · 1985
This paper surveys a number of efficient randomized algorithms for selection and sorting which we derive from inefficient deterministic specifications. Along with these derivations, we simultaneously derive bounds on the probability distribution of the sequential and parallel time cost of these algorithms. There are several potential benefits of this work. We develop, for the first time, general techniques for deriving randomized algorithms from deterministic specifications. Previous derivations only considered deterministic algorithms. Furthermore, our derivations encompass many known sequential and parallel randomized algorithms for selection and sorting which required separate proofs and probabilistic analysis. Also, we present a new randomized comparison sorting algorithm that takes 0(loglogn) time and uses n1+ epsilon processors to sort n keys.