A problem related to selection is that of determining the k smallest elements of a sequence S (in any order). On a sequential computer this can be done as follows: First determine the kth smallest...

A problem related to selection is that of determining the k smallest elements of a sequence S (in any order). On a sequential computer this can be done as follows: First determine the kth smallest element (using SEQUENTIAL SELECT); then one pass through S suffices to determine the k - 1 elements smaller than k. The running time of this algorithm is linear in the size of S. Design a parallel algorithm to solve this problem on your chosen submodel of each of the following models and analyze its running time and cost: (i) shared-memory SIMD, (ii) interconnection-network SIMD, and (iii) specialized architecture.