3011 3012 Give an Olg ntime EREW algorithm to perform the pr

30.1-1

30.1-2

Give an O(lg n)-time EREW algorithm to perform the prefix computation on an array x[1. . n]. Do not use pointers, but perform index computations directly.

30.1-3

Suppose that each object in an n-object list L is colored either red or blue. Give an efficient EREW algorithm to form two lists from the objects in L: one consisting of the blue objects and one consisting of the red objects.

30.2-8

Complete the proof of Theorem 30.1 by describing how a concurrent read on a p-processor CRCW PRAM is implemented in O(lg p) time on a p-processor EREW PRAM.

30.5-2

Given a 6-coloring of an n-object list, show how to 3-color the list in O(1) time using n processors in an EREW PRAM.

30.5-3

Suppose that every nonroot node in an n-node tree has a pointer to its parent. Give a CREW algorithm to O(1)-color the tree in O(lg^*n) time.

Solution

LISTRANK(L)

for each processor i, in parallel

       do if next[i] = NIL

            then d[i] <- 0

            else d[i] <- 1

while there exists an object i such that next[i]!= NIL

     do for each processor i, in parallel

             do if next[i] != NIL

                  then d[i]<- d[i] + d[next[i]]

                        next[i]<- next[next[i]]

                                                                                                This algorithm computes the distances. It shows the list

                                                                                                just after initialization. In the first iteration, the first five list objects have

                                                                                                non-nil pointers, so that lines 8-9 are executed by their responsible processors.

                                                                                                An efficient parallel solution, requiring only O(lg n) time, is given by the

                                                                                                above parallel pseudocode.