1. Given a sequence of numbers {a1, a2, ... , an}, show how to compute the prefix sum in constant time using PRAM. Which PRAM is used, how many processors are needed, and what is the cost of this algorithm?
2. Design an algorithm to distribute a copy of a sequence X = {x1, x2, ... , xk} that is stored in global memory to the local memory of each processor in O(log n) time, assuming you have an n-processor EREW PRAM and k =O(log n).
3. The suffix sum (or suffix maxima) was briefly discussed in class and is defined in our textbook by Akl. The prefix maxima can be computed by first reversing the sequence, then computing its prefix sum, and finally reversing the results of this computation. Provide a formal description of this PRAM algorithm and analyze its running time and cost. (Note: A formal description is illustrated by the one on slide 31 of our PRAM slide chapter.)
4. Show the simulation of CR by EREW PRAM. This is problem 30.2-8 in the Cormen, et. al. reference. NOTE: This is similar to the simulation of CW by EREW PRAM covered in slides. Recall that for a CW simulation, values must be carried from processors to memory. However, for the CR simulation, values must be carried from the selected memory cells back to the processors that are reading a memory cell value.
5. Give an O(lg n)-time EREW algorithm that determines for each object in an n-object list whether it is in the middle object. (Note: The middle object is defined to be the object in the |n/2|position.)