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.
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.