PART
- A (10 x 2 = 20 MARKS)
ANSWER
ALL THE QUESTIONS
1.
|
Define
big Oh notation with suitable expression.
|
2.
|
Give
two examples for NP hard problem.
|
3.
|
Give
an example of Fibonacci heap and define Fibonacci heap.
|
4.
|
Define
binomial heap with appropriate diagram.
|
5.
|
Define
AVL trees and example.
|
6.
|
What
is the purpose of Red black trees?
|
7.
|
What
is the run time complexity of Quick Sort?
|
8.
|
Define
the advantages of greedy algorithms?
|
9.
|
What
are the advantages of dynamic programming?
|
10.
|
List
two example problems which can be solved by back tracking.
|
PART
- B (3 x 10 = 30MARKS)
ANSWER
THE ANY THREE
11.
|
a)
Explain the following class of algorithms with the examples:
(OR)
b) Explain the
insertion and deletion algorithm for circular multiply doubly linked list
with head nodes. (16)
|
12.
|
a)
Discuss an algorithm find the nth smallest value from a Max heap and binary
search tree. Compare. (16)
(OR)
b) Discuss, compare
and contrast binomial heaps and Fibonacci heaps in terms of insertion, deletion
operations and applications. (16)
|
13.
|
Describe
any one scheme for implementing Red-Black Trees. Explain insertion and
deletion algorithm with details. How do these algorithms balanced the height
of the tree? (16)
(OR)
Explain
the data structure, Insertion deletion operation and applications for Tries.
(16)
|
14.
|
(a)
(i) Write algorithm for Quick Sort. (8)
(ii)
Write intermediate steps to perform Quick Sort for the following:
5,25,4,33,6,9,47,50,2. (8)
(OR)
(b)
Write algorithm for Tree Vertex Splitting. (16)
|
15.
|
(a)
Describe how Eight Queen’s problem can be solved using back tracking. Write
the algorithm. (16)
(OR)
(b)
State the Knapsack Problem and explain how it can be solved using branch and
bound algorithm. (16)
|
No comments:
Post a Comment