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

Printed Pages:02Sub Code:RCA303

Paper Id: __214303__Roll 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-
- What is convex hull?
- Minimum weight spanning tree.
- 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 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:

**4. Attempt any one part of the folloing:**

**7 x 1 = 7**

- Prove that if . Then
- 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
- Draw a binomial heap whose keys are elements of A.
- 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 , , and 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?