2 3 4 Floyd-Warshall (W) 1 nW.rows create n x n array D for i = 1 to n for j = 1 to n 5 D[i, j] = W[i, j] 6 for k = 1 to n 7 for i 1 to n 8 9 for j = 1 to n D[i, j] = min(D[i, j], D[i,k] + D[k, j]) 10 return D (a) Design a parallel version of this algorithm using spawn, sync, and/or parallel for as appropriate. (Copy and modify the pseudocode.) Think carefully about what can be parallelized and what can't, and explain your choices. (b) Analyze the asymptotic runtime of your algorithm in terms of its work, span, and parallelism. Show that the sum of the eigenvalues is a + d (called the trace of A) and the product is ad- be (the determinant of A). (Hint: Use the quadratic formula.) 4. Give a direct (i.e., without Lemma 9.5) proof of Lemma 9.4 when A is a diagonal matrix. (Use the form of eat and the definition of norm from Section 4.) Lemma 9.4: ustment of the LEMMA 9.4 Let =+ inj, j = 1, 2, ..., n be the eigenvalues of the matrix A (repe- titions allowed). Let o> max (c). Then there is a constant, K> 0, such that if X(t) is a fundamental matrix of (9.1), then ||X(t)|| Ket The proof of this lemma is easy if A is a diagonal matrix and is not very difficul using the properties of norms listed in Section 4, if A is similar to a diagon matrix. For the general case we need to use the Putzer algorithm. We state t basic fact as another lemma. Lemma 9.5 (DO NOT USE TO PROVE LEMMA 9.4): LEMMA 9.5 Let A, , and 2; be as in Lemma 9.4 and let r() be the elements in the decomposition (7.1) of e. Then ,(t) Scie where c, is a positive constant. Proof. The proof is by induction. Let A, i=1, 2, ..., n be given and let et be expressed by (7.1). Clearly, Ir(t) = lese. Suppose tha (t)ce,j=1, 2,..., i-1. Then, solving the scalar differential equa tion (or using the variation of constants formula, for the scalar-1 x matrix-equation),