30.1-1 30.1-2 Give an O (lg n )-time EREW algorithm to perform the prefix comput
ID: 3928590 • Letter: 3
Question
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.
Explanation / Answer
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.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.