Birla Institute of Technology (BIT Mesra) 2005 MS Software Engineering Design and Analysis of Algorith(closed book) - Question Paper

Birla Institute of Technology and Science, Pilani
Distance Learning Programmes Division
MS Software Engineering in Collaboration with Wipro Technologies
First Semester 2005 – 2006
Mid semester
Regular
Course No. : SEWP ZG511
Course Name : Design and Analysis of Algorithms
Nature of examination : Closed Book Exam
weightage : 40 %
Duration : 2Hours
Date : July 02, 2005 (FN)
Note: Attempt all ques.. begin every ans from a fresh page

1. The Master’s Theorem has been given beneath for your reference.
The Master Theorem: Let a ? one and b > one be constants, let f(n) be a function, and let T(n) be described on the nonnegative integers by the recurrence
T(n) = aT(n/b) + f(n)
where we interpret n/b as ?n/b? or ?n/b? Then T(n) can be bounded asymptotically as follows:
1. If f(n) = O(nlogba – e) for a few constant e > 0, then T(n) = ?(nlogb a).
2. If f(n) = ?(nlogba ), then T(n) = ?(nlogba lg n).
3. If f(n) = O(nlogba + e) for a few constant e > 0, and if af(n/b) ? cf(n) for a few constant c<1, and all sufficiently large n, then T(n) = ?(f(n)).
Solve the subsequent recurrence relations using Master’s Theorem. (3 * 5)

(a) T(n) = four T(n/2) + n
(b) T(n) = four T(n/2) + n2
(c) T(n) = four T(n/2) + n3

2. Construct the optimal prefix code for the subsequent data, clearly showing the Huffman tree at every step. Mention clearly, at the last step, the optimal prefix code for every of the characters.
(5)
Words And The For But Then So Go
Frequency 3450 4400 1500 2000 1000 2000 3200

3. Write the complete algorithm (in the form of a pseudo-code) that takes the optimal prefix tree and an encoded string as inputs and produces the decoded string as output. The function could be of the form

Decode(Tree, encodedString) (10)




4. Write a complete algorithm that does the following:

a. Accepts as parameter two long positive numbers (unlimited number of digits), in the form of two long strings
b. Adds the two numbers by extracting 1 digit every from the two strings
c. Creates a 3rd string which represents the sum of the two long numbers

The function could be of the form

AddLong (Number1, Number 2) (10)






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

Earning:   Approval pending.