Teaching

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.

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.

Teaching

User Tools

Site Tools

Page Tools