Given an array of integers, find the index of the first positive element in the array. For example, if the array contains the following five elements: -3, -1, 4, -5, 6. The first positive element is 4. Thus, the index is 2. This is a very simple problem and can be solved as follows:

At the end, if variable posIndex is negative, all elements in array a[] are negative; otherwise, the value of posIndex is the desired index.posIndex = -1; for (i = 0; i < n; i++) if (a[i] > 0) { posIndex = i; break; }

How can we solve this problem using multiple threads? In fact, a possible
solution is very similar to the
**maximum finding** problem.
For any two different elements of the input array, say
** a[i]** and

- Both
and*a*[*i*]are positive. In this case, we can cross out*a*[*j*]because it cannot be the first positive element of array*a*[*j*].*a*[ ] - Both
and*a*[*i*]are negative. In this case, we can cross out*a*[*j*]*both*, because neither of them is a positive element of array.*a*[ ] -
is positive and*a*[*i*]is negative. In this case, we can cross out*a*[*j*]because it cannot be the first positive element of*a*[*j*].*a*[ ] -
is negative and*a*[*i*]is positive. In this case, we can cross out*a*[*j*]because it cannot be the first positive element of array*a*[*i*].*a*[ ]

Index |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

Value |
-1 | -3 | 5 | -2 | 6 | -7 | -8 | 4 | 5 |

The following shows how the cross-out procedure proceeds:

i |
a[i] |
j |
a[j] |
Case |
Result |

0 | -1 | 1 | -3 | case (2) | cross out both |

2 | 5 | case (4) | cross out a[0] |
||

3 | -2 | case (2) | cross out both | ||

4 | 6 | case (4) | cross out a[0] |
||

5 | -7 | case (2) | cross out both | ||

6 | -8 | case (2) | cross out both | ||

7 | 4 | case (4) | cross out a[0] |
||

8 | 5 | case (4) | cross out a[0] |
||

1 | -3 | 2 | 5 | case (4) | cross out a[1] |

3 | -2 | case (2) | cross out both | ||

4 | 6 | case (4) | cross out a[1] |
||

5 | -7 | case (2) | cross out both | ||

6 | -8 | case (2) | cross out both | ||

7 | 4 | case (4) | cross out a[1] |
||

8 | 5 | case (4) | cross out a[1] |
||

2 | 5 | 3 | -2 | case (3) | cross out a[3] |

4 | 6 | case (1) | cross out a[4] |
||

5 | -7 | case (3) | cross out a[5] |
||

6 | -8 | case (3) | cross out a[6] |
||

7 | 4 | case (1) | cross out a[7] |
||

8 | 5 | case (1) | cross out a[8] |
||

3 | -2 | 4 | 6 | case (4) | cross out a[3] |

5 | -7 | case (2) | cross out both | ||

6 | -8 | case (2) | cross out both | ||

7 | 4 | case (4) | cross out a[3] |
||

8 | 5 | case (4) | cross out a[3] |
||

4 | 6 | 5 | -7 | case (3) | cross out a[5] |

6 | -8 | case (3) | cross out a[6] |
||

7 | 4 | case (1) | cross out a[7] |
||

8 | 5 | case (1) | cross out a[8] |
||

5 | -7 | 6 | -8 | case (2) | cross out both |

7 | 4 | case (4) | cross out a[5] |
||

8 | 5 | case (4) | cross out a[5] |
||

6 | -8 | 7 | 4 | case (4) | cross out a[6] |

8 | 5 | case (4) | cross out a[6] |
||

7 | 4 | 8 | 5 | case (1) | cross out a[8] |

From the above, we learn that ** a[2]** is never crossed out, and,
hence the index is 2! That is,

The following summarizes this cross-out algorithm:

- Suppose the input array
has*a*[ ]*n*elements. - Prepare an array
of*w*[ ]*n*elements. - Create
*n*threads so that thread*i*writes a 1 into, indicating that*w*[*i*]is not crossed-out.*a*[*i*] - For every pair of
*i*<*j*, create a thread*T*_{i,j}to handle elementsand*a*[*i*]. Write 0 into*a*[*j*],*w*[*i*], or both based on the four cases stated above to indicate the corresponding element is crossed-out. Thus, we need*w*[*j*]threads.*n**(*n*-1)/2 - Up to this point, array
has all the information we want. Store -1 into variable*w*[ ].*p* - For 0 <=
*i*<*n*, create threads*X*_{i}to examine. If*w*[*i*]contains a 0, do nothing; otherwise, write the value of*w*[*i*]*i*into variable.*p* - Thus, if the value of
is not negative, it is the desired index, and*p*is the first positive element of*a*[*p*]. Otherwise, there is no positive element in*a*[ ].*a*[ ]

Write a program that reads in an array of some integers and use the above
algorithm to find its first positive element.
Will you be able to simplify the above cases?
**Note that you should aim for maximum parallelism.
More precisely, all created threads should run concurrently.**