a) Give an O(log n) time, O(n) work EREW algorithm, which, given a boolean array A of size n, finds the smallest index k such that A[k] = 1. You may assume that such a k exists. Also, your solution should not change array A (i.e, you will need to do any computation in another array.)
Perform Prefix-Sums on A, placing the result into B.
For 1<=i<=n pardo:
If (A[i] and (B[i] = 1)):
Answer := i
B[i] will be precisely 1 only if there is at most one 1 in A before and including index i. If this is the case, then the only way A[i] can also be true is if i is the single unique answer.
b) Give an O(1) time, O(n2) work common CRCW algorithm for the same problem.
For 1<=i<=n pardo:
B[i] := 0
For 1<=j<i pardo:
If (A[j]):
B[i] := 1
If (A[i] and not B[i]):
Answer := i
This algorithm records into the B array if there are any 1's before the specified index. If the answer to that is no, and there is a 1 in that index of the A array, that is the answer. Otherwise, it is not.
