Design and Analysis of Algorithm 2018- MCA 2nd year AKTU

Printed Pages:02Sub Code:RCA303

Paper Id: 214303Roll No. _____________________

MCA

(SEM-III) THEORY EXAMINATION 2018-19

DESIGN & ANALYSIS OF ALGORITHM

Time: 3 Hours
Total Marks: 70

Note: 1. Attempt all Sections. If require any missing data; then choose suitably.

SECTION A

1. Attempt all questions in brief.2 x 7 = 14

Disuss the basic steps in the complete development of an algorithm.
Define the Longest common subsequence (LCS).
If the height of a heap is h, what will be the maximum and minimum no. of elements in a heap?
What do you understand by ‘stable’ sort?
Define various asymptotic notations in short.
Explain NP hard problems and NP complete.
What are randomized algorithms?

SECTION B

2. Attempt any three of the folloing:7 x 3 = 21

What is divide and conquer strategy and explain the binary search with suitable example.
Distinguish between Quick sort Merge sort, and arrange the following numbers in increasing order using merge sort.18, 29, 68, 32, 87, 24, 47, 50
What is single source shortest path problem? Solve the shortest path problem using Dijkastra’s algorithm.
What are approximation algorithms? Give an approximation algorithm for travelling salesman problem (TSP).
Write the short note of the following-
1. What is convex hull?
2. Minimum weight spanning tree.
3. Hamiltonian cycles.

SECTION C

3. Attempt any one part of the folloing:7 x 1 = 7

State algorithm of quick sort and prove that Quick sort algorithm takes $O(n^{2})$ time to sort the array of n elements in the worst case?
Sate master’s theorem and find the time complexity for the following recurrence:

$T(n)=2T(n^{\frac{1}{2}})+\log n$

4. Attempt any one part of the folloing:7 x 1 = 7

Prove that if $f(n)=a_{m}n^{m}+a_{m-1}n^{m-1}+.........+a_{1}n+a_{0}$ . Then $f(n)=O(n^{m})$
Define a red black tree. Draw the red black tree resulting from inserting the numbers 41, 38, 31, 12, 19,8 into an initially empty RB Tree.

5. Attempt any one part of the folloing:7 x 1 = 7

Let
1. Draw a binomial heap whose keys are elements of A.
2. Apply the extract min operation on the resulting heap.
What do you understand by amorized analysis? What are different methods used for it. Explain one of them with suitable example.

6. Attempt any one part of the folloing:7 x 1 = 7

Describe the Warshall’s and Floyd’s algorithm to finding all pair shortest path. Also, give the time complexity of both algorithm.
Define knapsack problem and describe its formation. Find the optimal solution to the knapsack instance $n=5$ , $W=[20, 30, 40, 10, 7]$ , $P=[7, 8, 9, 1, 6]$ and $C=80$ using greedy method.

7. Attempt any one part of the folloing:7 x 1 = 7

Write the prim’s algorithm to find the minimum cost spanning tree of a undireced graph and compare their time complexity.
Discuss the string matching algorithm. Can we put it into the problem category?