CS计算机代考程序代写 algorithm Root Finding / pointer jumping Problem:

Root Finding / pointer jumping Problem:
Show the steps of the pointer jumping-based PRAM algorithm for finding the roots of the forest below. What are the parallel time and work for a forest of maximum depth h?
Solution:
All nodes now point to the root node of the tree they belong to, and so we¡¯re done. So the PARM algorithm takes two units of time for this input instance.
For a forest of maximum depth h, the parallel time of the PRAM algorithm would be O(log h) and the work performed would be O(n log h).

Problem:
Given a forest with 64 nodes comprised of four trees of 16 nodes each. The depths of the four trees are 3, 7, 8 and 15. How many iterations of pointer jumping are required for finding the root of each node of the forest in parallel?
Solution:
4 iterations
Time dominated by tree of max height (15 in this case) 15 -> 8 -> 4 -> 2 -> 1

Problem:
What are T(n) and W(n) for the following PRAM algorithm:
Solution:
T(n) = O(log n), W(n) = O(n log n). This is the PRAM algorithm for list ranking with pointer jumping.

Problem:
Show the steps in the point jumping based PRAM algorithm for list ranking. The array S below gives the successor of node I (0 <= I <= 6). For the last node in the list, S[i] is set to -1. Show how R(i), the distance of each node from the end of the list, can be computed. Solution: Problem: Show the steps in the pointer jumping-based PRAM algorithm for list ranking. The array S below gives the successor of node I (0 <= I <= 6). For the last node in the list, S[i] is set to -1. Show how R(i), the distance of each node from the end of the list, can be computed. Node 0 1 2 3 4 5 6 S 2 3 5 -1 1 6 4 Solution: Initialization: After 1 iteration of pointer jumping After 2 iterations After 3 iterations Node 0 1 2 3 4 5 6 Q 2 3 5 -1 1 6 4 R 1 1 1 0 1 1 1 Q 5 3 6 -1 3 4 1 R 2 1 2 0 2 2 2 Q 4 3 1 -1 3 3 3 R 4 1 4 0 2 4 3 Q 3 3 3 -1 3 3 3 R 6 1 5 0 2 4 3