Birla Institute of Technology (BIT Mesra) 2005 MS Software Engineering Design and Analysis of Algorith(open 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
Comprehensive exam
Regular
Course No. : SEWP ZG511
Course Name : Design and Analysis of Algorithms
Nature of examination : Open Book Exam Bangalore
weightage : 60 %
Duration : 3Hours
Date : September 18, 2005 (FN)

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

Instructions
• Answers must be written clearly. Untidy work will fetch lower marks
• Diagrams must be drawn clearly and legibly. Untidy work will fetch lesser credit.


1. Illustrate the operation of HEAPSORT on the array A = {5, 13, 2, 25, 7, 17, 20, 8, 4}. Show, visually, the binary tree just after the BUILD-HEAP is called and at the end of every of the HEAPIFY operation. (6)

2. Construct the prefix function p for the trend abcabcab using the Knuth-Morris-Pratt algorithm. It is sufficient to draw the final look-up table. You need not show the complete steps of the algorithm. (6)

3. Write a complete, replaced Rabin-Karp algorithm for matching trends on a text that is known to have characters from the set of alphabets {a, b, c, d, e, f, g, h, i}.
(8)

4. Write a complete Greedy algorithm for the Fractional Knapsack issue. The issue is described as follows:

A thief robbing a store obtains n items every item worth vi dollars and weighs wi pounds. The thief has a knapsack of capacity W pounds (the thief can carry a total weight of not more than W pounds). The thief is allowed to carry all the volume available of an item or a fraction thereof. What items should the thief take and how much of every of those items to maximize the value of the theft? (10)



5. Draw the look-up table, based on the Dynamic Programming method, for the 0-1 knapsack issue. The data is given in the table beneath. give the final optimal solution, too. (10)

Item Weight Value
1 3 10
2 2 8
3 4 11
4 5 13
5 3 12

6. Determine a LCS of the strings <1, 0, 0, 1, 0, 1, 0, 1> and <0, 1, 0, 1, 1, 0, 1, 1, 0>. It is sufficient to show the look-up table (along with the relevant arrows) and the solution. You need not show the intermediate steps. (10)


7. Write a complete algorithm that determines if a provided number is a perfect number or not. Use the subsequent definition of a perfect number. The algorithm should take 1 parameter, the number, and print a message that says if the number is perfect or not.

A number N (greater than 0) is stated to be perfect if the sum of all its factors equals the number. For example, six is a perfect number because one + two + three = 6, and 1, two and three are factors of 6. 28 is also a perfect number because one + two + four + seven + 14 = 28, and the individual numbers are all factors of 28. (10)




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

Earning:   Approval pending.