Biju Patnaik University of Technology 2007-5th Sem B.Tech Computer Science and Engineering ANALYSIS AND DESIGN OF ALGORITHMS CLASS TEST-2 - Question Paper

ANALYSIS AND DESIGN OF ALGORITHMS 5TH SEM CLASS TEST-2 MAX. MARKS-10
ans any 5 ques.. All ques. carry equal marks.

1.Instead of partition into 2 equal parts in binary search, if we partition into 2/3 and 1/3, obtain out the recurrence of binary search for worst case analysis. Draw the recursion tree.
2.Suppose we are comparing implementations of insertion sort and merge sort on the identical machine. For inputs of size n, insertion sort runs in 8.n^2 steps, while merge sort runs in 64 n lg n steps. For which values of n does insertion sort beat merge sort?
3.Write the algorithm of Merge sort and obtain its worst case running time.
4.Illustrate the operation of MAX-HEAPIFY(A,3) on the array A=<27,17,3,16,13,10,1,5,7,12,4,8,9,0>
5.What do you mean by a Heap?Write an algorithm of HeapSort(). Show that the time complexity for HeapSort() is O(n lg n)
6.Use the substitution method to prove that the recurrence T(n)=T(n-1)+T(n) has the solution T(n)=T(n^2)

Earning:   Approval pending.