A F1008 Pages: 4

}
b) Explain the advantages of using height Balanced Trees? Explain AVL Rotations. (4)

c) Find the minimum and maximum height of any AVL-tree with 7 nodes? Assume that the height ofa (2)
tree with a single node is 0.
7 8) List the Properties of B-Trees. (2)
0) A 2-3-4 tree is defined as a B-Tree with minimum degree 1-2. Create a 2-3-4 tree by (4)
successively inserting the inserting the elements (in the given order) 42,56, 24, 89, 1, 5, 87,
8. 61. 6, 78, 7, 12, 34.
c) Delete the elements 89, 78. 12 and 8 from the above resultant tree. (3)
PART C
Answer all questions, each carries3 marks.
8 Ina weighted graph, assume that the shortest path from a source ‘s’ to a destination ‘t’ is correctly (3)
calculated using ௨ shortest path algorithm. Is € following statement true?
If we increase weight of every edge by 1, the shortest path always remains same. Justify your answer
with proper example.
9 Define Strongly Connected Components of a graph. (3)
Write the algorithm to find Strongly Connected Components in a graph.
10 Write an algorithm to merge two sorted arrays and analyse the complexity. (3)
11 Write notes on Dynamic Programming Approach. List the sequence of steps to be followed in (3)

Dynamic Programming.

PART 0
Answer any two full questions, each carries9 marks.
12 a) State Shortest Path Problem and Optimal substructure of Shortest Path. (2)
b) Write Dijkstra’s Single Source Shortest path algorithm. Analyse the complexity. (4)

c) Find the shortest path from s to all other vertices in the following graph using Dijkstra’s Algorithm. (3)

13 a) Write the algorithm for DFS and analyse its complexity. (4)
b) Multiply the following two matrices using Strassen’s Matrix Multiplication Algorithm. (5)

Page 2 of 4