Reference no: EM131756282

1. For this problem and the next you may use any of the algorithms developed in class as subroutines. Just be sure to specify the input to the algorithm, and what operation is performed. For instance, prefix "sum" can be used as prefix SUM, or prefix MULT, or prefix MAX, etc.

a) Develop an O(log n) time, O(n) work EREW algorithm, which given A[1..n], an array of integers, writes into location FIRST, the smallest index k such that A[k] = 1. You may assume that such a k exists.

b) Give an O(1) time, O(n) work common CRCW algorithm for the same problem.

Hint: First give an O(1) time, O(n) work common CRCW algorithm for determining if an array contains a 1. Then give an O(1) time, O(n²) work common CRCW algorithm for determining the least i such that A[i] = 1. Finally, use these as subroutines in conjunction with partitioning A into segments of  elements.