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

24views

written 6.8 years ago by

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 t₁ (n) ε0(g₁ (n)) and t₂(n)ε 0(g₂(n)),
then t₁(n)+t₂ε 0(max {g₁(n), g₂(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,

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)

ADD COMMENT EDIT