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.