Homework #7

#1. Apply the F matrix method in our class handout (i.e. the Floyd-Warshall algorithm) to the directed graph above to calculate and show the matrices F⁽⁰⁾, F ⁽¹⁾, F ⁽²⁾ , F ⁽³⁾ , F ⁽⁴⁾ , F ⁽⁵⁾ , F ⁽⁶⁾ with the vertex order v1, v2, v3, v4, v5, v6 on rows and columns.

#2. Continue from problem #1. Based on the matrices F⁽⁰⁾ and F ⁽⁶⁾ alone without visual help from the graph above, demonstrate how you can determine the shortest distance from v2 to v5 and how to reconstruct a shortest path from v2 to v5.

NOTE that the matrices denoted by the notation F ⁽ⁱ⁾ here are different from the matrices D⁽ⁱ⁾ derived by the matrix method used in Homework #6.

#3. Revisit the big O notation defined in Section 3.9 and consider the following three functions f(n) = 1024 n², g(n) = n⁴, and h(n) = 2ⁿ. Which of the following statements are correct?

(i) f(n) = O( g(n) ), (ii) f(n) = O( h(n) ),

(iii) g(n) = O( f(n) ), (iv) g(n) = O( h(n) ),

(v) h(n) = O( f(n) ), (vi) h(n) = O( g(n) ).

#4. Explain why the D matrix method for finding all-pair shortest distance information has a time complexity f(n)=O(n⁴) while the F matrix method for finding all-pair shortest distance information has a time complexity f(n)=O(n³ ) given that n is the number of vertices in the graph. In other words, for each method (i) estimate the time complexity f(n) as the number of basic arithmetic operations and comparisons needed when applying the method to a graph of n vertices and (ii) show that f(n) = O(n⁴) for the D matrix method and f(n) = O(n³) for the F matrix method.