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. 

<code>
For 1<=i<=n pardo:
   If (A[i] and (B[i] = 1)): 
      Answer := i
</code>

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.

<code>

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
         
</code>

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.