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

4 YEAR B.TECH. DEGREEE EXAMINATION---APRIL 2007
3rd YEAR exam
2nd SEMESTER
Computers Science & Engineering
DESIGN AND ANALYSIS OF ALGORITHMS
(Revised Regulations w.e.f 2003-2004)
Time: three Hours] [Max.Marks :100
ans any 5 ques. choosing 1 ques. from every unit
All ques. carry equal marks
UNIT-I
1. (a) Write an algoritm for multiplying 2 square matrices of order n.
(b) What is the time complexity of the abeve algoritm?Explain.
Or
2. (a) Write a recurssive algorithm for computing 2^n = 2^(n-1)+2^(n-1) for any positive integer n
(b) Draw a tree of recurssive calls for this algorithm and count the number of calls made by the algorithm

UNIT-II
3. (a) Write a pseudo code for a divide and conquer algorithm for finding values of both the largest and the smallest elements in any array of n numbers
(b) Apply quick sort algorithm to sort the list E,X,A,M,P,L,E in alphabetical order. Draw the tree of recurssive calls made
Or
4. (a) Write an algorithm for depth 1st search of a graph and discuss with an example
(b) Write an algorithm for insertion sort
UNIT-III
5. (a) Construct a 2-3 tree for the list 9,5,8,3,2,4,7
(b) Write an algorithm for constructing an AVL tree for a list of n distinct integers
Or
6. (a) Construct a heap for the list 1,8,6,5,3,7,4 by successive key insertions (top-down algorithm)
(b) Write an algorithm for finding the largest key in a B-Tree
UNIT-IV
7. (a) define Warshall's algorithm for finding the transitive closure of a digraph
(b) Write an algorithm for finding an optimal binary search tree
Or
8. (a) Prove that any weightd connected graph with distinct weights has exactly 1 minimum spanning tree
(b) define Dijkstra's algorithm for single source shortest path issue
UNIT-V
9. (a) Draw a decision tree and obtain the number of key comparisons for the worst and avg. cases for the three-element basic bubble sort
(b) Write a recursive backtracking algorithm to obtain all the Hamiltonian sysles of a provided graph
Or
10.(a) discuss the terms: NP-Hard and NP Complete issues
(b) explain in detail abut n-queens problem

Earning:   Approval pending.