JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD MCA-II Semester Regular Examinations July 2010 DATA STRUCTURES AND ALGORITHMS

Code No: 21

Time: 3hours
Max.Marks:60


Answer any Five questions
All questions carry equal Marks

1. a) Define big O, omega and theta notations
b) Find the theta notation for the number of times the statement x=x+1 is executed in the following cases
i) i=2;
while(i=1)
{
for (i=0;i j=j/3;
}
c) Write ADT for linear list

2. a) Write a function invert that invert the contents of stack in to another stack using stack operations. If original stack contains 1,8,5,3 with 1 being most recently added item in the stack, the other stack after insert contains 3,5,8,1 with 3 being item at the top of stack.

b) Consider the following recursive functionint bbb(int n, int r)
{
if (r==0 || n==r) return 1;
else return bbb(n-1,r)+bbb(n-1,r-1);
}
Demonstrate run time stack contents for the function call bbb(5,3). How many times bbb is invoked? What is the maximum depth of the stack?

3. a) Write an algorithm that returns the number of terminals in the given binary tree.
b) Define binary min heap. Construct min heap for the following input.
75 6 27 86 15 8 33

4. a) With an example, explain the representation of disjoint sets along with union and find operations.

b) Explain different ways of representing directed graphs along with their merits and demerits. Give space complexity of each representation.

5. a) Write recursive algorithm for quick sort.
b) Derive time complexity of quick sort algorithm
c) Demonstrate quick sort algorithm for the following data.
15 25 8 33 1 12 6 60

6. Define B-tree. What are the applications of B-tree? Construct B-tree for the following sequence of keys 25 5 8 17 20 12 15

7. a) Write control abstraction for greedy method.
b) With an example, explain single source shortest path problem along with algorithm.

8. Trace Knuth-Morris-Pratt algorithm for the occurrence of pattern “cancan” in “cacancacanccancanca”. How many comparisions did the algorithm make?