Birla Institute of Technology (BIT Mesra) 2006 DATA STRUCTURES AND ALGORITHMS - Question Paper

Birla Institute of Technology & Science, Pilani

Distance Learning Programmes Division

Second Semester 2006-2007

Mid-Semester Test (EC-1 Regular)



Course No. : IS ZC361

Course Title : DATA STRUCTURES AND ALGORITHMS

No. of Pages = 1

No. of ques. = five
Nature of examination : Closed Book

Weightage : 40%

Duration : two Hours

Date of examination : 04/02/2007 (AN)

Note:

1. Please follow all the Instructions to Candidates provided on the cover page of the ans book.

2. All parts of a ques. should be answered consecutively. every ans should begin from a fresh page.

3. Mobile phones and computers of any type should not be brought inside the exam hall.

4. Use of any unfair means will outcome in severe disciplinary action.



Q.1. Consider the subsequent algorithm

arrayFind(x, A)

Input : An element x and an n element array A

Output : The index i such that x = A[i] or

-1 if no element of A is equal to x

i =0 ;

while( i < n ) {

if(x==A[i])

return i;

else i = i+1; }

return –1;



(i) compute the worst case running time of this algorithm.



(ii) presume that the elements are sorted. Rewrite the algorithm arrayFind(x, A) whose worst case running time is O(log n) and show that the running time is O(log n).



(iii) Suppose we have an algorithm, find2D, to obtain an element x in a 2 dimensional nxn array A. The algorithm find2D iterates over the rows of A and calls the algorithm arrayFind on every 1 until x is obtained or it has searched all rows of A. What is the worst case running time of this algorithm (a) if the elements in every row are sorted? (b) if the elements in every row are not sorted ? (3 + four + four = 11)



Q.2. Consider the subsequent recursive equation, defining a function T(n) :



T(n) = three if n = 1

T(n-1) + 2n otherwise.



Show by induction, that T(n) = 2n+1-1. (4)



Q.3. provide an example of a worst-case-sequence with n elements for insertion-sort, and show that your example correspond to the worst case running time. (4)



Q.4. Write an algorithm BottomUpHeap(S) whose input is a sequence S storing n = 2h-1 keys and output is a heap T storing the keys in S. obtain the running time of the algorithm in big O notation. (10)



Q.5 (a) Consider the statement : The order in which a fixed set of elements is inserted into a binary search tree does not matter – the identical tree outcomes every time. If this statement is actual discuss why it is actual. Otherwise provide 1 example to show that the statement is false.



Q.5 (b) Show that the height of an AVL tree T storing n items is O(log n). (4 + seven = 11)



********

Earning:   Approval pending.