Explain the term 'average ease time complexity' of a sorting algorithm. What is it for the Quick Sort algorithm Give reasons for your response.
Explain the matrix chain multiplication algorithm. Do not write any pseudocode.

2.(a) Give the running time analysis of the Insertion Sort algorithm.
How can two polynomials be multiplied using FFT What is the running time of this procedure?

3.(a) Insert the following sequence of numbers in a binary search tree, showing the binary search tree after each insertion:

5,2,1,18,16,10,15,9

Delete 5 from this tree, and show the resulting tree.
Sort the following numbers using the Merge Sort algorithm

30,5,25,10,31,42,26

4.(a) Give the different ways of representing undirected graphs. Further, show the representation for the following example:

V
E Explain the 'union by rank' and the 'path compression' heuristics for the linked list representation of disjoint sets.

5.(a) Write the recursive GCD algorithm, and run it for GCD(30, 21). What is the running time of this algorithm
Given a sequence of 10,000 numbers in an increasing order, except for 10 of them which are not in this order. Which sorting algorithm should be used to arrange them in sorted order Give reasons for your answer.

6.(a) Illustrate all the steps of the Kruskal's algorithm for finding a minimum spanning tree of the following graph: <img src='./qimages/12503-6a.jpg'>
Define 'flow network' and Show that if f1 and f2 are flows, then

af1 f2 is also a flow,

where 0 binary search tree on n nodes has height a (log2 Is this statement true Give reasons for your answer.