Carleton University
Technical Report TR-219
February 1993
Three Algorithms for Selection on the Reconfigurable Mesh
Dipak Pravin Doctor & Danny Krizanc
Abstract
We present three algorithms for selection on the reconfigurable mesh (RMESH) model. The first, deterministic, algorithm runs in O(blog* N) time on an N processor RMESH, for N integers each of length ::; b-bits. The second, deterministic, algorithm runs in expected O(logN) time on an N processor RMESH for N elements drawn from a linearly ordered universe. The third, randomized, algorithm runs in O(log2N) time, with high probability on an N processor RMESH again for N elements drawn from a linearly ordered universe. Our algorithms address three different scenarios and are important in view of a previous O(log2(N)) algorithm [EW91} requiring complicated data movements operations.