Sri Venkateswara University (SVU) 2008 B.Tech Computer Science and Engineering Design and Analysis of Algorithms - Question Paper

4 YEAR B.TECH DEGREE EXAMINATION, APRIL 2008
3rd year exam
2nd Semester
Computer Science & Engineering
Design and Analysis of Algorithms
(Revised Regulations w.e.f 2003-2004)


Time: three hours Maximum marks:100

ans any FIVE, choosing 1 ques. from every unit.
All ques. carry equal marks.

UNIT-I
1. (a) Write the important characteristics of algorithms. (7M)
(b) describe the different Asymptotic notations and their representations. (7M)
(c) How do you evaluate the performance of the algorithms? (7M)
or
2. (a) Write the recursive and non-recursive algorithms for the generation of Fibonacci numbers. (10M)
(b) Derive the time complexity of every of the methods in the above issue. (5M)
(c) Solve the subsequent recursive equation:


C1 if n<=2
T(n) =
2T(n/2)+c2 if n>2 (5M)

UNIT-II
3. (a) Write the Topological sorting algorithm and discuss (7M)
(b) Write the insertion sort algorithm quote in which circumstances this algorithm is preferred.
(6M)
(c) Identify the number of exchanges to be made to the array of n items on sorting them (in ascending order) using the above algorithm for the subsequent category of input. (7M)
(i) 100,75,69,40,30,12,5
(ii) 5,17,6,4,0,20,32,15
or
4. (a) Write the algorithm for sequential search (8M)
(b) Write the divide and conquer algorithm for merge sorting (12M)

UNIT-III
5. (a) Write notes on balanced search trees (7M)
(b) What is meant by Presorting? discuss. (6M)
(c) discuss the concept of Heapify. Also derive the time complexity. (7M)
or
6. (a) Write briefly about space and time trade offs.(7M)
(b) Write summary on string matching (7M)
(c) provide an example for B-Trees (6M)

UNIT-IV
7. (a) discuss the solution optimal storage on tapes using dynamic programming method (10M)
(b) describe principle of optionality. discuss how it applies to traveling sales man issue. (10M)
or
8. (a) How multi-stage graphs differ from the general graphs. discuss the approaches to derive solutions from multistage graph. (10M)
(b) Apply the dynamic programming method for the subsequent 0/1 Knapsack issue instance: (10M)
w1 = p1 +(100,50,20,10,7,3) n=6 and m=165

UNIT-V
9. (a) Write a summary on approximation of algorithms (10M)
(b) discuss about P, NP and NP-Complete issues (10M)
or
10.(a) Write the Back tracking algorithms for sum of subsets issue (10M)
(b) Write the Branch and Bound solution for Knapsack issue and discuss. (10M)

Earning:   Approval pending.