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