Birla Institute of Technology (BIT Mesra) 2004 MS Software Engineering Data Structure & Algorith(open book) - Question Paper

Birla Institute of Technology and Science, Pilani
Distance Learning Programmes Division
MS Software Engineering in Collaboration with Wipro Technologies
Second Semester 2003 – 2004
Comprehensive exam
Regular
Course No. : SEWPZC415
Course Name : Data Structure & Algorithms
Nature of examination : Open book examination
weightage : 60 %
Duration : 3Hours No of pages : 2
Date : July 18, 2004 No. of questions : 8

Note: Attempt all ques.. begin every ans from a fresh page

1 Solve the subsequent recurrence relations (6)


x(n) =




x(n) =


2. Write a recursive algorithm to calculate 2n for any non-negative integer n which is based
on the formula 2n = 2n-1 + 2n-1 (2)

3. Apply quicksort to sort the list E,X,A,M,P,L,E in alphabetical ordering. (3+1+2+1)
a) Write the best case input for the quick sort
b) Find the best case time efficiency of quick sort
c) Are arrays made up of all equal elements the worst-case input, the best-case input, or
neither?

4. Write an algorithm for the construction of a heap. Create heap for the subsequent items
10, 15, 30, 25, 50, 20, 45 (3+5)

5. Write th Horspools’s algorithm to count the number of occurrences of a trend string in the provided string. obtain the shift table for the trend ‘BARBER’ (8)


6. Solve all pairs shortest path issue for the digraph with the weight matrix (12)







7. What is an AVL tree? discuss the need for rotation of AVL trees. Construct an AVL tree for the list 6, 5, 4, 3, 2, one by successive insertions. Clearly show the steps. (12)

8. Construct a Huffman code for the subsequent data: (5)

Character A B C D -
Probability 0.1 0.2 0.1 0.3 0.15





------------------------------

Earning:   Approval pending.