Question 1 : What is the formula to compute the transitive closure of a graph?
1. tij(k) = tij(k-1) AND (tik(k-1) OR tkj(k-1))
2. tij(k) = tij(k-1) OR (tik(k-1) AND tkj(k-1))
3. tij(k) = tij(k-1) AND (tik(k-1) AND tkj(k-1))
4. tij(k) = tij(k-1) OR (tik(k-1) OR tkj(k-1))
5.
View Answer   Discuss with Members

Question 2 : In the given graphHow many intermediate vertices are required to travel from node a to node e at a minimum cost?
1. 2
2. 0
3. 1
4. 3
5.
View Answer   Discuss with Members

Question 3 : In the given graph What is the minimum cost to travel from vertex 1 to vertex 3?
1. 3
2. 2
3. 10
4. -3
5.
View Answer   Discuss with Members

Question 4 : The time taken to compute the transitive closure of a graph is Theta(n²).
1. True
2. False
3.
4.
5.
View Answer   Discuss with Members

Question 5 : What happens when the value of k is 0 in the Floyd Warshall Algorithm?
1. 1 intermediate vertex
2. 0 intermediate vertex
3. N intermediate vertices
4. N-1 intermediate vertices
5.
View Answer   Discuss with Members

Question 6 : Complete the program.

n=rows[W]D(0)=Wfor k=1 to n     do for i=1 to n          do for j=1 to n                 do ________________________________return D(n)

1. dij(k)=min(dij(k-1), dik(k-1) – dkj(k-1))
2. dij(k)=max(dij(k-1), dik(k-1) – dkj(k-1))
3. dij(k)=min(dij(k-1), dik(k-1) + dkj(k-1))
4. dij(k)=max(dij(k-1), dik(k-1) + dkj(k-1))
5.
View Answer   Discuss with Members

Question 7 : Who proposed the modern formulation of Floyd-Warshall Algorithm as three nested loops?
1. Robert Floyd
2. Stephen Warshall
3. Bernard Roy
4. Peter Ingerman
5.
View Answer   Discuss with Members

Question 8 : Floyd- Warshall algorithm was proposed by ____________
1. Robert Floyd and Stephen Warshall
2. Stephen Floyd and Robert Warshall
3. Bernad Floyd and Robert Warshall
4. Robert Floyd and Bernad Warshall
5.
View Answer   Discuss with Members

Question 9 : What procedure is being followed in Floyd Warshall Algorithm?
1. Top down
2. Bottom up
3. Big bang
4. Sandwich
5.
View Answer   Discuss with Members

Question 10 : Floyd Warshall Algorithm can be used for finding _____________
1. Single source shortest path
2. Topological sort
3. Minimum spanning tree
4. Transitive closure
5.
View Answer   Discuss with Members