A A6810 Pages: 4

successive deletion of the keys in the order 8,12,1, 41.
7 a) Explain the important properties of B-Tree.
b) Construct a B-tree of minimum degree 3 by inserting the elements in the order

given F, Q,P,K,A,L,R,M,N,X,Y,D,Z,E,H,T,V,W,C. from the constructed tree

delete A,P,Q,R,T.
PART C
Answer all questions, each carries 3 marks.
8 List and explain the characteristic properties associated with a problem that can

be solved using dynamic programming.

9 Let G be a weighted undirected graph with distinct positive edge weights. If
every edge weight is increased by same value, will the minimum cost spanning
tree and shortest path between any pair of vertices change. Justify your answer.

10 Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij
in the matrix W below is the weight of the edge {i, j}. What is the minimum
possible weight of a spanning tree T in this graph such that vertex 0 is a leaf

node in the tree T?

0 1 8 1 4
1 0 12 4 9
W=/8 12 0 7 3
1 4 7 0 2
49 3 20,
11 Let (u,v) be a minimum-weight edge in a graph G. Show that (u,v) belongs to
some minimum spanning tree of G.
PART D

Answer any two full questions, each carries 9 marks.
12 a) Write down DFS algorithm and analyse the time complexity. What are different

classification of edges that can be encountered during DFS operation and how
itis classified?

b)

Page 2 of 4

(2)
(7)

(3)

(3)

(3)

(3)

(4)

(5)