Q1. Calculate the connected components of the graph G = (V, E) where
V = {a, b, c, d, e, f, g, h, i, j, k}
and edges E are preprocessed in the given order:
(d, i) (f, k) (g, i) (b, g) (a, h) (i, j)
(d, k) (b, j) (d, f) (g, j) (a, e) (i, d)
By using the disjoint set data structure operations.
Q2. Illustrate the steps to make the heap that outcome if the following keys are inserted to an initially empty heap.
41 28 33 15 25 7 12
Q3. Assume that the given character array is to be sorted through the heap sort algorithms.
Illustrate how the above data would be arranged in the array after the heap construction phase.
Q4. Assume that in 0-1 knapsack problem the order of items if sorted on increasing value is the same as their order if sorted by reducing weight. Write down an efficient algorithm to determine an optimal solution to the problem.
Q5. Write detail notes on any three of the given:
a) Radix sort
b) B trees
c) Floyd-Warshall Algorithm
d) Robin Karp string matching method