Question Paper: Design and Analysis of Algorithms : Question Paper Jun 2015 - Computer Science Engg. (Semester 4) | Visveswaraya Technological University (VTU)
0

## Design and Analysis of Algorithms - Jun 2015

### Computer Science Engg. (Semester 4)

TOTAL MARKS: 100
TOTAL TIME: 3 HOURS
(1) Question 1 is compulsory.
(2) Attempt any four from the remaining questions.
(3) Assume data wherever required.
(4) Figures to the right indicate full marks.
1 (a) Discuss the various stages of algorithm design and analysis process using a flow chart.(10 marks) 1 (b) Prove that : If t1 (n) ε0(g1 (n)) and t2(n)ε 0(g2(n)),
then t1(n)+t2ε 0(max {g1(n), g2(n)})
(6 marks)
1 (c) Consider the following algorithm :
Algorithm Mystery (n)
//input : A non negative integer n
S←0
for i←I to n do
S←s+1*1
return s
i) What does this algorithm compute?
ii) What is its basic operation?
iii) How many times is the basic operation executed?
iv) What is the efficiency class of this algorithm?
(4 marks)
2 (a) Write merge sort algorithm and discuss its efficiency. Sort the list E, X, A, M, P, L, E in alphabetical order using the merge sort.(10 marks) 2 (b) Design an algorithm for binary search, give an example. Show that the worst case efficiency of binary search is 0(log n)(10 marks) 3 (a) Solve the following instance of knapsack problem using greedy algorithm. Knapsack weight M = 20,

<colgroup span="4" width="85"> </colgroup>
 Item 1 2 3 Weight 18 15 10 Profit 25 24 15
(4 marks) 3 (b) Using the Prim's algorithm, determine the minimum cost spanning tree for the graph of Fig. Q3 (b) (8 marks) 3 (c) Design the Dijkstra's algorithm and apply the same to find the single source shortest paths problem for the graph taking vertex 'a' as source in Fig. Q3(c). (8 marks) 4 (a) Define transitive closure of a graph. Write Warshall algorithm to compute transitive closure of a directed graph. Apply the same on the graph defined by the following adjacency matrix.
$$\begin{bmatrix} 0 &1 &0 &0 \\0 &0 &1 &0 \\0 &0 &0 &1 \\0 &0 &0 &0 \end{bmatrix}$$
(10 marks)
4 (b) Using Floyd's algorithm, find all pair shortest path for the graph of Fig. Q4(b). (6 marks) 4 (c) Write a note on travelling sales person problem(4 marks) 5 (a) Write insertion sort algorithm. Apply it to arrange the following numbers in increasing order 89, 45, 68, 90, 29, 34, 17.(8 marks) 5 (b) Design a BFS algorithm to check the connectivity of a given graph.(8 marks) 5 (c) What is time-space trade off of an algorithm?(4 marks) 6 (a) Write short notes on :
i) Tight lower bound
ii) Trivial lower bound
iii) Information-theoretic lower bounds
(12 marks)
6 (b) Define decision tree? Draw the decision tree to sort the elements using insertion sort(8 marks) 7 (a) Write the pseudo code for backtracking algorithm. Apply backtracking to solve the instance Of the sum of subset problem : S = {3, 5, 6, 7} and d = 15.(10 marks) 7 (b) With the help of a state space tree, solve the travelling salesman problem of Fig. Q7(b), using branch-and-bound algorithm. (10 marks) 8 (a) What is prefix computing problem? Write the algorithms for prefix computation which uses: i) n processors ii) n/log n processors(10 marks) 8 (b) Let the input to the prefix computation problem be 5, 12, 8, 6, 3, 9, ll, 12, l, 5, 6, 7, 10, 4, 3, 5, and ⊕ Let stand for addition. Solve the problem using work optimal algorithm.(10 marks)