| Title: | A CONSTANT-TIME SELECTION ALGORITHM ON AN LARPBS |
| DOI No: | 10.1142/9781860948534_0010 |
| Source: | INNOVATIVE APPLICATIONS OF INFORMATION TECHNOLOGY FOR THE DEVELOPING WORLD (pp 68-72)
|
| Author(s): | MICHAEL AROCK
Department of Computer Applications, National Institute of Technology, Tricky 620 015, Tamilnadu, India
R. PONALAGUSAMY
Corresponding author.
Department of Mathematics, National Institute of Technology, Trichy 620 015, Tamilnadu, India
|
| Abstract: | The selection problem is to determine the qth smallest element in a set S of n elements, for any given positive integer q. This paper proposes a parallel algorithm for the problem on a Linear Array with a Reconfigurable Pipelined Bus System (LARPBS). The algorithm requires constant time only on an LARPBS of O(n) processors, where |S| = n. We claim that the algorithm is cost optimal, as it matches with the sequential lower bound Ω(n). The algorithm employs simple prune-and-search strategy. |
| Full Text: | View full text in PDF format (244KB) |
| TOC: | Back to Table of Contents |
|
|
