Design and Analysis of Algorithm | Nagpur University | Win-18

B.E. (Computer Science Engineering ) Fifth Semester (C.B.S)

Design & Analysis of Algorithms

NIR/KW/18/3437

Max. Marks- 80
Time- Three Hours

Notes : 1. All questions carry marks as indicated.
2. Solve Question 1 OR Questions No. 2.
3. Solve Question 3 OR Questions No. 4.
4. Solve Question 5 OR Questions No. 6.
5. Solve Question 7 OR Questions No. 8.
6. Solve Question 9 OR Questions No. 10.
7. Solve Question 11 OR Questions No. 12.
8. Due credit will be given to neatness and adequate dimensions.
9. Assume suitable data whenever necessary.
10. Illustrate your answers whenever necessary with the help of neat sketches.

1. a) Define algorithm in detail. Explain their four distinct area of study.   [06 M]

b) Solve the following recurrence relation using characteristic equation.   [07 M]

OR

2. a) Solve the following using master method.     [08 M]
1)  T(n) = 9T(n/3)+n
2) T(n) = T(2n/3)+1
3) T(n)= 4T(n/2)+n
4) T(n)=3T(n/4)+n log n

b) Find the time complexity for following algo-Algorithm sum (a [ ], n)   [05 M]
{
S = 0.0;
for j = 1 to n do
s = s + a [ i ] ;
return s;
}

3. a) Explain the process of deleting a node from Fibonacci Heap structure. Draw all the modification if minimum value is deleted from tree.     [07 M]

b) What are different asymptotic notation? Explain them briefly for the following equation find the values of constant using various approach.     [07 M]
i) 3n +2
ii) 10n²+4n+2

OR

4 a) What is sorting network? Explain bitonic sorting network for the following set of information 1, 5, 7, 2, 8, 6, 2, 9. Explain its advantages.     [07 M]

b) Give stepwise operation on Heap sort. on following input array & also explain the complexity of heap sort.  ( 4, 8, 20, 17, 7, 25, 2, 13, 5 )     [07 M]

5. a) Schedule the following jobs using job scheduling algorithm. Also write an algorithm for sane.  [07 M]

b) For the following knapsack sequence of objects find profit by three methods. Capacity =11, n = 4 w = (1, 2, 5, 8, 7) p = (1, 6, 18, 25, 30)    [06 M]

OR

6. a) Generate the Huffman code for following 6 characters given below:  [06 M]

b) Write an algorithm for binary search. Find out no. of comparison required for successful & unsuccessful search on following array. – 12, 22, 34, 45, 56, 78, 91, 103, 114, 118, 125    [07 M]

7. a) Find the minimum cost path from ‘s’ to ‘t’ in multistage graph. Shown using forward approach.    [07 M]

b) What is travelling salesman problem. Implement travelling salesman problem for following matrix.  [06 M]

OR

8. a) Write an algorithm to generate LCS. Apply algo. for following string & generate LCS.  [07 M]
X = a, a, b, a, a, b, a, b, a, a.
Y = b, a, b, a, a, b, a, b.

b) Find the minimum no. of multiplication required to multiply the matrices of given
dimension.  [06 M]
A = 10 ×20, B= 20× 13, C= 13 ×15, D= 15× 12  .

9. a) Explain 8 Queen problem. Explain the explicit & implicit constraints associated with this
problem. Give at least two solution for this problem.  [08 M]

b) Solve the following using sum of subset method.  [06 M]
w = 15, 5, 10, 20
m = 30

OR

10. a) What is the use of Hamiltonian cycle? Implement Hamiltonian cycle on following graph. [07 M]

b) What is graph coloring? Color the following graph using graph coloring algorithm.  [07 M]

11. a) Explain the following NP problem with respect to graph.    [09 M]
1) Clique                                                   2) Graph partitional into triangle
3) Independent set problem

b) Prove that    P ⊆ NP    [04 M]

OR

12. a) Explain P, NP, NP complete, & NP-Hard with suitable example.  [08 M]

b) Write an algorithm for non deterministic searching & sorting  [05 M]