Search ...
Results
Subscribe
Step-by-Step Solutions
University Majors
Support Hub
Legal & Support Articles
Contact Us
Login
Share
Search ...
Results
Subscribe
Step-by-Step Solutions
University Majors
Support Hub
Legal & Support Articles
Contact Us
Login
Share
Information Technology
Algorithms Illuminated: Greedy Algorithms and Dynamic Programming
46 SOLVED PROBLEMS
Question: 18.P.6
(S) The Floyd-Warshall algorithm runs in O(n³) time on graphs with n vertices and m edges, whether or not the input graph contains a negative cycle. Modify the algorithm so that it solves the all-pairs shortest path problem in O(mn) time for input graphs with a negative cycle and O(n³) time ...
Verified Answer:
Modify the input graph G = (V,E) by adding a new s...
Question: 18.P.4
(S) For the input graph what are the final array entries of the Floyd-Warshall algorithm from Section 18.4? ...
Verified Answer:
With columns indexed by k and rows by vertex pairs...
Question: 18.P.5
(S) For the input graph what are the final array entries of the Floyd-Warshall algorithm? ...
Verified Answer:
With columns indexed by k and rows by vertex pairs...
Question: 18.P1
(S) For the input graph what are the final array entries of the Bellman-Ford algorithm from Section 18.2? ...
Verified Answer:
With columns indexed by i and rows by vertices:
Question: 18.6
Let G = (V,E) be an input graph. What is L0,v,w in the case where: (i) v = w; (ii) (v,w) is an edge of G; and (iii) v ≠ w and (v,w) is not an edge of G? a) 0, 0, and +∞ b) 0, ℓvw, and ℓvw c) 0, ℓvw, and +∞ d) +∞, ℓvw, and +∞ (See Section 18.4.6 for the solution and discussion) ...
Verified Answer:
Correct answer: (c). If v = w, the only v-w path w...
Question: 18.3
What’s the running time of the Bellman-Ford algorithm, as a function of m (the number of edges) and n (the number of vertices)? (Choose the strongest true statement.) a) O(n²) b) O(mn) c) O(n³) d) O(mn²) (See Section 18.2.9 for the solution and discussion.) ...
Verified Answer:
Correct answer: (b). The Bellman-Ford algorithm so...
Question: 18.5
Do you see any bugs in the argument above? (Choose all that apply.)a) The concatenation P* of P*1 and P2 need not have origin v. b) P* need not have destination w. c) P* need not have internal vertices only in {1, 2, . . . ,k}. d) P* need not be cycle-free. ...
Verified Answer:
Correct answer: (d). The concatenation
P^{*...
Question: 18.4
How many invocations of a single-source shortest path subroutine are needed to solve the all-pairs shortest path problem? (As usual, n denotes the number of vertices.) a) 1 b) n − 1 c) n d) n² (See Section 18.3.3 for the solution and discussion.) ...
Verified Answer:
Correct answer: (c). One invocation of the single-...
Question: 18.2
How many candidates are there for an optimal solution to a subproblem with the destination v? (Let n denote the number of vertices in the input graph. The in- and outdegree of a vertex is the number of incoming and outgoing edges, respectively.) a) 2 b) 1 + the in-degree of v ...
Verified Answer:
Correct answer: (b). The optimal substructure lemm...
Question: 18.1
Consider an instance of the single-source shortest path problem with n vertices, m edges, a source vertex s, and no negative cycles. Which of the following is true? (Choose the strongest true statement.) a) For every vertex v reachable from the source s, there is a shortest s-v path ...
Verified Answer:
Correct answer: (a). If you give me a path P betwe...
Loading...
Load More Questions