Design and Analysis of Algorithms in C++ 4. 130 Points] Short answers (be brief

Question

Design and Analysis of Algorithms in C++

4. 130 Points] Short answers (be brief and to-the-point; do not use trivial cases to establish f A. Can Floyd's algorithm be used in place of Dijkstra's algorithm? Briefly explain how or why not. B. While applying the Warshall's algorithm to an adjacency matrix A of a directed graph, a column had all O's in the transitive closure T. If this is not possible briefly explain why not. If briefly explain under what condition will it happen? . while running the Warshall's algorithm, after two successive iterations k and k+1, RKT but R was I. If this is not possible briefly explain why not. If it is possible, briefly explain m, D(i, value was e in iteration k and was 14 in iteration k+1. Briefly explain what just happened. E. Can Floyd's All-Pairs-Shortest-Path algorithm be used to find the reachability between pairs of vertices- "can a vertex i be reached from a vertex j in a directed graph?". If so, briefly explain how it can be done. Otherwise, briefly explain why not. F. Under what condition will the path of the robot in the Robot Coin Collection Problem be unique? (i.e., there will not be multiple paths leading to the optimal solution) G. How many multiplications are done in the Horner algorithm discussed in class (p235) in the evaluation of P(x) 4x-6x +x-2r+3, for some value of x? H. How many multiplications done in t he RightLeftBinaryExponentiation algorithm discussed in class (p238) in the computation of al?

Explanation / Answer

ANSWER 4

a) Yes, Floyd's algorithm can be used in place of Dijkstra's algorithm asBoth Floyd’s and Dijkstra’s algorithm may be used for finding the shortest path between vertices. The biggest difference is that Floyd’s algorithm finds the shortest path between all vertices and Dijkstra’s algorithm finds the shortest path between a single vertex and all other vertices. The space overhead for Dijkstra’s algorithm is considerably more than that for Floyd’s algorithm. In addition, Floyd’s algorithm is much easier to implement.

b)

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.