(In evaluation of solutions, the ideas behind the solutions are given the hightest importace - syntactic correctness is much less important, however not insignificant. Remember that even partial answers can yield many points.)
1. Explain the following shortly.
(a) How arbitary CRCW (program) works? (2 pts)
(b) What does Brent's theorem claim? What is the meaning of it? (2 pts)
(c) What is pointer jumping? Where is it applied? What can you say about its running time? (2 pts)
2. Present and analyze as fast (possibly randomized) work optimal algorithm for maximum finding as you can. Do not use the SCAN models (Sum, Minimum, Strong, ...). What model your algorithm uses? (Max 6 pts; fast algorithm gives more points than slow)
3. (i) What does P-completeness mean and what is its importance for parallel computing? (3 pts)
(ii) What basic parallel algorithmic techniques you know? Explain them shortly. (3 pts)
4. How Sollin's algorithm for determining the minimum weight spanning tree in a weighted graph works? (Just explain the ideas; you do not need to write the algorithm)
With Sollin's algorithm, solve the MST for a graph, whose weight matrix is the following. Show, how the algorithm proceeds.
a |
b |
c |
d |
e |
f |
g |
|
a |
1 |
7 |
9 |
||||
b |
1 |
6 |
4 |
5 |
|||
c |
7 |
6 |
12 |
8 |
|||
d |
9 |
12 |
11 |
2 |
|||
e |
4 |
10 |
|||||
f |
5 |
8 |
11 |
10 |
3 |
||
g |
2 |
3 |
Missing number means missing arc. (6 pts)
5. Present a parallel algorithm for finding the maximal subsum, maximal prefix sum, and maximal suffix sum in an integer vector and analyze it. Note that some elements may be negative, and chosen elements must be successive. For example, in (2, -3, 2, 5, 3, -7, 2, -3, 6), maximal subsum is 10, maximal prefix sum is 9, and maximal suffix sum is 8. (6 pts)