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