Derivation of Randomized Algorithms.
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1985
- Accession Number
- ADA161358
Entities
People
- John Reif
- Sanguthevar Rajasekaran
Organizations
- Harvard University