|
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.
|