DATA STRUCTURES AND ALGORITHMS - JANUARY 2013

Question Paper Code: 68089

M.E./M.Tech. DEGREE EXAMINATION, JANUARY 2013

First Semester

Computer Science and Engineering

CS9212/241102/8241102/CS912 – DATA STRUCTURES AND ALGORITHMS

(Common to M.Tech. –Information Technology and M.Tech. Information and Communication Technology)

(Regulation 2009)

Time: Three hours	Maximum:100 marks

Answer ALL questions.

PART A – (10 x 2=20 marks)

1.      If a 2-dimentional array A[0..10, 1..10] is stored using row major representation, then what is address of A[3,5]? (Assume 2 bytes for one element).

2.      What are NP-complete problems and why are they so important?

3.      Define the height balanced tree.

4.      Find an optional solution to the Knapsack problem for each instance n=4, (P1, P2, P3, P4) = (10, 10, 12, 18), (W1, W2, W3, W4) = 2, 4, 6, 9 n=15.

5.      Compare 2-3 tree with 2-3-4 trees.

6.      Write the procedure for recursive function to construct a binary tree.

7.      Define the principle of optimality.

8.      Discuss in short the branch and bound methodology.

9.      Let I=10, n=4, (I1,I2, I3, I4) =2, 4, 5, 6. Find the optimal storage scheme for all programs.

10.  What are B-tree and M-way search trees? List two differences.

PART  B – (5 x 16 – 80 marks)

11.	(a)	(i)	Describe asymptotic notation with several parameters with the help of an example.                                                                                          (8)
		(ii)	Find the time and space complexity for the non-recursive algorithm to fine the   Fibonacci sequence.                                                             (8)
			Or
	(b)	(i)	Explain amortized analysis with an example.                                     (8)
		(ii)	Solve the recurrence relation for the algorithm:                                              Cube S(n){                                                 If n=1, return 1;                                                 Else                                                             Return S(n-1) + n * n * n;                                                        }                                                    (8)
12	(a)		Develop the algorithm for insertion and deletion into Max heap.
			Or
	(b)		Develop the algorithm Lazy-binomial heaps for insertion and deletion.
13.	(a)		Illustrate with an algorithm to show the insertion of data into an AVL tree.
			Or
	(b)		Write an algorithm to merge two AVL trees T1 and T2 to obtain new AVL tree pointed out by NT
14.	(a)		Discuss in detail the various algorithms to solve the convex hull problem.
			Or
	(b)		Explain “Quick Sort” technique. Show that it is of O(n * log 2 n).
15.	(a)		Let L=10, n=6 (I1, I2, I3, I4) = (5, 6, 3, 7, 5, 4). Find the optimal bin packing of the six objects using three bins.
			Or
	(b)		Consider the Knapsack problem instance with n=8 objects, size of knapsack =m = 110, p={11, 21, 31, 33, 43, 53, 55, 65} and w={1, 11, 21, 23, 33, 43, 45, 55}. Find the optimal solution using back tracking.

                                               

What is the running time of QUICKSORT when all elements of array A have the same value?

My Solution
The running time of QUICKSORT when all elements of array A have the same value will be equivalent to the worst case running of QUICKSORT since no matter what pivot is picked, QUICKSORT will have to go through all the values in A. And since all values are the same, each recursive call will lead to unbalanced partitioning.

Thus the recurrence will be:

T(n)=T(n−1)+Θ(n)

The above recurrence has the solution (I will prove this later):

T(n)=Θ(n2)

Hence the running time of QUICKSORT in this case is

Θ(n2)

CS9212 DATA STRUCTURES AND ALGORITHM QUESTION PAPERS - JANUARY 2010

PART - A (10 x 2 = 20 MARKS)

ANSWER ALL THE QUESTIONS

1.	Consider the two functions f (n) =3n^2+5 and g (n) =n^2. Prove with graphical representation that asymptotic upper bound of f (n) is g (n)?
2.	Solve the recurrence equation of Merge sort to show that the worst-case complexity is O (nlogn)?
3.	Define Null Path length? What is the role of NPL in Leftist Heap?
4.	Is the height of every tree in a Binomial heap that has n elements O (log n)? If not what is the worst-case height as a function of n?
5.	What is the maximum and minimum height of a binary tree with 28 nodes? Mention the suitable tree traversal to sort the values in increasing order?
6.	Compare the worst case height of a red-black tree with n nodes and that of an AVL tree with the same number of nodes?
7.	Why it is necessary to have the auxiliary array billow: high in function Merge? Give an example that shows why-in-place merging is insufficient?
8.	Find an optimal placement for 13 programs on three tapes T0, T1 and T2. Where the programs are of lengths 12,5.8,3,2,7,5.1,8.2,4,3,11,10, and 6.
9.	Give an example of a set of knapsack instances for which |s^i| = 2^I, 0<i<n. Your set should include one instance for each n.
10.	Present a backtracking algorithm for solving the knapsack optimization problem using the variable tuple size formulation.

PART - B (5 x 16 = 80MARKS)

ANSWER ALL THE QUESTIONS

11.	(a) (i) Write algorithm to perform in order and preorder traversal of binary tree. (8) (ii) Explain about recurrence equation with an example. (8) (OR) (b) (i) Explain the principle of Amortized Analysis. (10) (ii) Write algorithm to insert a node in the beginning of a list. (6)
12.	12.       (a) Write algorithm to construct Fibonacci heap with suitable example. (16) (OR) (b) Write algorithm to construct Binomial heap with suitable example. (16)
13.	(a) (i) Construct a B-tree to insert the following (order of the tree is 3)     5,25,3,75,4,43,6,8,10     (ii)What are the properties of Red black trees? (4) (OR) (b) (i) What is the need for splay trees? Give an example. (8)
14.	(a) (i) Discuss Strassen’s matrix multiplication as well as classical O (n^2) one. Determine when Strassen’s method outperforms the classical one. (8)      (ii) Code the divide and conquer algorithm DCHull () in C++ and last it in appropriate data. (8) (OR) (b) Code and distinguish the JS and FJS functions for job sequencing with suitable data. Analyze the complexities of these two functions. (16)
15.	(a) Find the minimum cost path from S to T in the multistage graph of the given figure. Do this first using forward approach and then using backward approach. (16) (OR) (b) Give an n x n chess board, a knight is placed on an arbitrary square with coordinates (x, y). The problem is to determine (n^2-1) knight moves such that every square of the board is visited once if such a sequence of moves exists. Write a C++ program to solve this problem. (16)