Design and Analysis of Algorithms - May 2016

VTU Computer Science (Semester 4)

Total marks: --
Total time: -- INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary 1(a) Define big oh, omega and theta notations' for analyzing algorithm. Give at least one example for each. 10 marks

1(b) Write a algorithm for selection sort in ascending order. Show that its complexity is O(n²) and sort the following list 65, 50, 21, 43, 10, 15. 10 marks

1(c) Write the algorithm for sequential search, obtain the time complexity of this algorithm for successful and unsuccessful search in the worst case and best case. 10 marks

2(a) Explain the concept of divide and conquer. Design an algorithm for merge sort and derive time complexity. 10 marks

2(b) Write a algorithm for Quick sort, and sort the following number's 10, 8, 5, 15, 25, 75, 12. Obtain its time complexity. 10 marks

3(a) Obtain the optimal solution for the job sequencing problem with deadline, where n = 4 profit (P₁, P₂, P₃, P₄) = (100, 10, 15, 27) and dead lines (d₁, d₂, d₃, d₄) = (2, 1, 2, 1). 10 marks

3(b) Explain the concepts of greedy technique for prim's algorithm. Obtain minimum cost spanning tree for the graph whose weight matrix is given below $$\left[\begin{array}{ccccc}0& 3& \infty & 7& \infty \\ 3& 0& 4& 2& \infty \\ \infty & 4& 0& 5& 6\\ 7& 2& 5& 0& 4\\ \infty & \infty & 6& 4& 0\end{array}\right]$$<script type="math/tex; mode=display" id="MathJax-Element-1">\begin{bmatrix} 0 & 3 & \infty & 7 & \infty\ 3 & 0 & 4 & 2 & \infty\ \infty & 4 & 0 & 5 & 6\ 7 & 2 & 5 & 0 & 4\ \infty & \infty & 6 & 4 & 0 \end{bmatrix}</script> 10 marks

3(c) Write a Kruskal algorithm to find minimum cost spanning tree and obtain spanning tree of the graph shown below:
10 marks

4(a) Write Floyd's algorithm and solve the all pair shortest path problem for the graph shown below :
10 marks

4(b) Write a algorithm for Knapsack problem for dynamic programming and solve the following instance of the knapsack problem,
n = 4, weights (w₁, w₂, w₃, w₄) = (2, 1, 3, 2), profit (p₁, p₂, p₃, p₄) = (12, 10, 20, 15) Capacity W=5. 10 marks

5(a) Explain the concept of decrease and conquer method, indicating the three major variations of the same with examples. 10 marks

5(b) Write insertion sort algorithm and obtain its time complexity. Apply insertion sort on these elements: 25, 75, 40, 10, 20. 10 marks

5(c) Write a algorithm to sort by counting method. Obtain its time complexity, sort by count for given data 25, 45, 10, 20, 50, 15. 10 marks

6(a) Explain the lower bound and trivial lower bound arguments. 10 marks

6(b) What is a decision tree? Obtain decision tree to find minimum of three numbers. 10 marks

6(c) Explain the P, NP and NP complete problems. 10 marks

7(a) What is a N-Queen's problem? Give the state space tree for solving 4 Queen problem for at least one solution? 10 marks

7(b) With help of a state space tree solve the following instance of the knapsack problem by the branch and bound algorithm
N=4 weight (w₁, w₂, w₃, w₄) = (4, 7, 5, 3)
Profit (p₁, p₂, p₃, p₄) = (40, 42, 25, 12)
W=10 capacity knapsack. 10 marks

7(c) Obtain the optimal solution for the given assignment problem as a matrix shown below using branch and bound method : 10 marks

8(a) What is a prefix computation problem? Give the algorithm for prefix computation which use i) n-processor ii) n/log n 10 marks

8(b) Explain the different types of computational models. 10 marks

8(c) Obtain the maximum speed up when P=10 and for various value of f=(0.5, 0.1, 0.01). 10 marks