212 PARALLEL ALGORITHMS
- Formally rewrite the standard sequential matrix multiplication to calculate
the shortest path as described at the end of Section 7.7.1. Use the graph in
Fig. 7.7 to verify your algorithm. - Give the details of the analysis of the shortest-path algorithm that uses paral-
lel matrix multiplication. Your analysis should be based on the matrix multi-
plication taking an O(N) run time and a cost of O(N^3 ). Your complete
answer will depend on your determination of how many times this will be
called and for what size of array. - Using three processors, trace the execution of the parallel minimum span-
ning tree algorithm on the graphs in question 1, starting at node A. Your
trace should show the nodes each processor is responsible for, as well as the
values that each processor returns for each pass. If you have also worked
problem 1 from Section 6.4.2, compare your answers from that sequential
algorithm and this parallel one.