# CS502 VU Current Midterm Fall 2012 Paper 8 December 2012

What is the effect of MaxHeapify (A,i) when i>heapsize [A]/2?

Draw binary tree of Matrix ((A1(A2,A3))(A4,A5))?

What is heap and heap order?

Define heap sort algorithm?

How edit distance is used for correct spelling?

What are the Total numbers of edit distance in Matrix?

Another Paper:

questions

1.An array having n elements,what is the probability of selection 1/n element as a pivot element(2 marks)

2- draw chain matrix multiplication table for initialization state(2 marks)

3- when quick sort don’t uses divide n conquer explicitly n the main procedure used in Q.S(3 marks)

4- how to calculate optimum solution for 0/1 knapsack problem(3 marks)

5-fabinocci sequnce ka question tha.n i was asked to make a recursive tree for fib(8)(5 marks)

6-an array of A1,A2,A3….An number was given.i don’t remember the statement but according to that scenario it was a stable sorting algorithm havin O(n log n) algorithm.i was asked to solve that array problem.which sortin algorithm best suits???(5 marks)

Another Paper:

What are the two steps generally involved while developing dynamic programming algorithm.                                                                                                                  (2)

How we build heap?                                                                                                   (2)

What are the applications of edit distance technique? Name any three                     (3)

Solve: T(n) =  (T(q − 1) + T(2 − q) + 2)                                                              (3)

What is the worst case running time for the bucket sort? What simple change is required in the algorithm to preserve its linear expected running time and makes it worst case time Θ(n log n)                                                                                                                 (5)

Given an unordered list of n x0, x1, x2, …, xn and elements is common, if there are atleast n/5 copies of it.We want to identify all the common numbers in our list. Give O(n log n) to solve the problem.                                                                                             (5)