Birla Institute of Technology (BIT Mesra) 2007 MS Software Engineering Design & Analysis of Algorith - Question Paper

Birla Institute of Technology and Science, Pilani
Distance Learning Programmes Division
MS Software Engineering in Collaboration with Wipro Technologies
Second Semester 2006 – 2007
Mid-semester exam
Regular
Course No. : SEWP ZG511
Course Name : Design & Analysis of Algorithms
Nature of examination : Closed Book Bangalore
Weightage : 40 %
Duration : two Hours No of pages : 1
Date : March 18, 2007 (FN) No. of questions : 5

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

Q1a) describe the following:
accurate Algorithm
Hard issues
Asymptotic Notations
Data Structures 1x4=4

Q1b) Illustrate the operation of merge sort on the array A= (3, 41, 52, 26, 38, 57, 9, 49) 4
Q2a) Briefly discuss any 2 methods of solving recurrence relation (expression for a recursive procedure) 4

Q2b) Show that the solution of T (n) = T (n/2) + one is O(lg n). 4

Q3a) discuss the logic of counting sort with a suitable example 4

Q3b) calculate the running time of quick sort for avg. case performance 4

Q4a) discuss with suitable diagrams any 1 method of handling the collision that occurs during hashing 4

Q4b) Write an algorithm for insertion of a node into Binary Search Tree and comment on the running time of inserting a node 3+1


Q5a) elaborate B-Trees ? What do you mean by the order of the B-tree ? 1+3

Q5b) explain with figures, the structure of root, internal and leaf node of B-tree. 4



***********************

Earning:   Approval pending.