Friday 1 February 2013

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.