Question

1. Warshall's Algorithm

To which other algorithm from our course is Wasrhall's Transitive Closure algorithm most structurally similar?

A) Dijkstra

B) Floyd

C) Kadane

D) Karatsuba

E) Kruskal

F) Prim

G) Strassen

2. Powers of Adjacency Matrix

Which is true of an Adjacency Matrix of a directed graph raised to the k-th power (A^k)

A) A^k ​[i]​[j] = 1 if there is an edge of length k from vertex i to vertex j

B) A^k ​[i]​[j] = 1 if there is an edge of total cost k from vertex i to vertex j

C) A^k ​[i]​[j] = 1 if there is an path of length k from vertex i to vertex j

D) A^k ​[i]​[j] = 1 if there is an path of total cost k from vertex i to vertex j

E) None of the above

3. Transitive Closure by Matrix Operations

Which best describes how to determine the Transitive Closure by arithmetic operations on the Adjacency Matrix?

A) Compute A^(n-1)

B) Compute A^n

C) Compute A^0 + A^1 + ... + A^(n-1) where + is standard addition (integers)

D) Compute A^0 + A^1 + ... + A^(n-1) where + is boolean addition (true/false)

E) Compute A^1 + A^2 + ... + A^n where + is standard addition (integers)

F) Compute A^1 + A^2 + ... + A^n where + is boolean addition (true/false)

4. Transitive Closure using DFS (Directed Graph)

What best represents the the time complexity of computing the Transitive Closure of a Directed Graph, assuming representation by an Adjacency Table

A) O(V)

B) O(E)

C) O(V+E)

D) O(VE)

E) O(V^2)

F) O(E^2)

For brevity, we have sometimes dropped the set-cardinality signs, i.e. writing O(V) and O(E) respectively instead of the more proper O(|V|) and O(|E|).

Answer 1

Answer to 1)- (B).

warshall's algorithm is structurally similar to Floyd's all-pair shortest path algorithm. actually Floyd's algorithm is a bit of modification/improvement of warshall's algorithm and hence it is called Floyd-warshall algorithm. finding transitive closure of a di-graph requires iterating over the set of all the paths in the graph which is perfectly done by warshall's algo but if you want find shortest distance b/w all pairs of nodes of di-graph then you use modified warshall's algo called Floyd's algo( Floyd-warshall algo).

Answer to 2)- (C) A^k ​[i]​[j] = 1 if there is an path of length k from vertex i to vertex j.

It's standard definition of power of adjacency matrix of di-graph.

Answer to 3)- (F) Compute A^1 + A^2 + ... + A^n where + is boolean addition (true/false).

In order to compute transitive closure by matrix operations you use above formula. It actually finds if there exists a path of any length from 1 to n b/w given two nodes and returns true if it indeed exists which is what you call transitive closure from a node.

Answer to 4) - (C) O(V+E).

Depth first search algo takes O(V+E) time to finish the search.(used for transitive closure)