Exercise 30.2-1, page 708 of the text. You needn't give the argument of the last sentence of the exercise. But keep in mind that each processor is supposed to end up with a copy of its root.
Trace the execution of the algorithm of Section 30.1.3 on the binary search tree constructed by successive insertion of the integers 5, 4, 1, 7, 6, 3, and 2 into an initially empty tree. Show at least the linked list constructed, and the result of each iteration during the parallel prefix computation.
Trace the execution of the algorithm of Section 30.4 for the operation of addition, on the list (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16). Assume that the four processors are assigned elements {1, 4, 12, 16}, {2, 5, 6, 14}, {3, 7, 13, 11}, and {8, 9, 10, 15} respectively, and that these assignments do not change between recursive calls. Assume that at each iteration, each processor selects the unselected element that is first in alphabetical order among the objects that it owns (ok, this is not really random).
Assume that the results of successive coin flips are as follows, where the jth value in the kth group is the result of the coin flip for processor j during iteration k: HHHT, HHHH, TTTT, HHTT, HTTH, HTTH, THTH, HTTH, THHT, HHHH, HHTT, TTHH, HHTH. You may not need all 13 iterations.