The goal of this problem is computing the transitive closure of a directed graph. Definition: Given...

Transcribed Image Text:

The goal of this problem is computing the transitive closure of a directed graph. Definition: Given a directed graph, find out if a vertex j is reachable from another vertex i for all vertex pairs (i, j) in the given graph. Here, reachable means that there is a path from vertex i to j. The reachability matrix is called transitive closure of a graph. Here is a simple example in Figure 1: 2 T (E) What is the value of O(1) and why? (F) What is the solution to the recurrence induction. Let the cor lexity of matrix have tight bounds on matmul yet!). T A T TT T 1 2 3 4 5 1TTTTT TTTT TTTT TTTT 2 3 4 5 Τ Τ Τ Τ 1 2 3 4 5 Figure 1: A is adjacency matrix for the input graph, C is the transitive closure matrix (A) For matrix A, what does A[i, j] represent? (B) For matrix A2, what does A[i, j] represent? (C) Explain how to use matrix multiplication (and addition) to solve this problem. In particular, what are the matrices that you are multiplying? (D) How many matrix multiplication do we have? Keep in mind how you can store results in order to stop redundant calculations. (Explain briefly). Now we want to show how to solve the problem more efficiently using Divide and Conquer. The input graph has n nodes (1...n). We divide the nodes into two sub-problems of size n/2 ([1...n/2] and [n/2+1...n]), and solve each half separately. Using Divide and Conquer, we need to stitch the two halves together, and O(1) matrix multiplications are sufficient. resulted from Divide and Conquer solution? Prove by ultiplication be O(n) for some 2 ≤ w ≤ 3 (we don't The goal of this problem is computing the transitive closure of a directed graph. Definition: Given a directed graph, find out if a vertex j is reachable from another vertex i for all vertex pairs (i, j) in the given graph. Here, reachable means that there is a path from vertex i to j. The reachability matrix is called transitive closure of a graph. Here is a simple example in Figure 1: 2 T (E) What is the value of O(1) and why? (F) What is the solution to the recurrence induction. Let the cor lexity of matrix have tight bounds on matmul yet!). T A T TT T 1 2 3 4 5 1TTTTT TTTT TTTT TTTT 2 3 4 5 Τ Τ Τ Τ 1 2 3 4 5 Figure 1: A is adjacency matrix for the input graph, C is the transitive closure matrix (A) For matrix A, what does A[i, j] represent? (B) For matrix A2, what does A[i, j] represent? (C) Explain how to use matrix multiplication (and addition) to solve this problem. In particular, what are the matrices that you are multiplying? (D) How many matrix multiplication do we have? Keep in mind how you can store results in order to stop redundant calculations. (Explain briefly). Now we want to show how to solve the problem more efficiently using Divide and Conquer. The input graph has n nodes (1...n). We divide the nodes into two sub-problems of size n/2 ([1...n/2] and [n/2+1...n]), and solve each half separately. Using Divide and Conquer, we need to stitch the two halves together, and O(1) matrix multiplications are sufficient. resulted from Divide and Conquer solution? Prove by ultiplication be O(n) for some 2 ≤ w ≤ 3 (we don't

Answer rating: 100% (QA)

A The element Aij in matrix A represents the existence of a directed edge from vertex i to vertex j ... View the full answer