Determine the sequence of pairwise matrix multiplication to


Question 1:

(a) Give the formal definitions of the following:

1. A graph

2. A tree

3. B+ tree

4. An undecidable problem

Question 2

Apply Kruskal's algorithm to find Minimum Spanning Tree for the following graph.

733_Find Minimum Spanning Tree.png

Weight of edge(1,2) = 10 Weight of edge(2,4) = 5 Weight of edge(6,4)=10

Weight of edge(1,4) = 20 Weight of edge(2,3) = 3 Weight of edge(6,5)= 3

Weight of edge(1,6) = 2 Weight of edge(3,5) = 15 Weight of edge(4,5)= 11

Question 3

Draw a simple, connected, weighted digraph with 5 vertices and 10 edges, each with unique edge weights. Identify one vertex as a "start" vertex and illustrate a running of the Bellman-Ford algorithm on this graph. Show the steps of the algorithm.

Question 4

Suppose that M1 is 2 x 10 matrix; M2 is a 10 x 5 matrix; M3 is a 5 x 20 matrix, and M4 is a 20 x 10 matrix. Use dynamic programming to determine the sequence of pairwise matrix multiplication to use. Show the steps of the algorithm.

Solution Preview :

Prepared by a verified Expert
Data Structure & Algorithms: Determine the sequence of pairwise matrix multiplication to
Reference No:- TGS0974359

Now Priced at $15 (50% Discount)

Recommended (97%)

Rated (4.9/5)