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

4views

written 8.1 years ago by

Design and Analysis of Algorithms - Jun 2012

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) If t₁(n) ∈ 0 (g₁ (n)) and t₂ (n) ∈ 0 (g₂ (n)), prove that t₁ (n)+ t₂ (n) ∈ 0 (max {g₁ (n), g₂ (n)}).(6 marks) 1 (b) If M(n) denotes the number of moves in tower of Hanoi puzzle when a disks are involved, give a recurrence relation for M(n) and solve this recurrence relation.(7 marks) 1 (c) Give an algorithm for selection sort. If C(n) denotes the number of times the algorithm is executed (n denotes input size), obtain an expression for C(n).(7 marks) 2(a) Assuming that n is a power of 2, solve the recurrence relation T(n)=2T (n/2) +2. Take T(2)=1 and T(1)=0.(5 marks) 2(b) If n∈[2^k-1, 2^k], prove that binary search algorithm makes at most K element comparisons for a successful search and either K-1 or K comparisons for an unsuccessful search.(6 marks) 2(c) Give an algorithm for merge sort.(5 marks) 2(d) Consider the numbers given below. Show how partitioning algorithm of quick sort will place 106 in its correct position. Show all the steps clearly.

106

117

128

134

141

(4 marks) 3 (a) Let J be a set of K jobs and σ= i₁, i₂, i₃,........, i_k be a permutation of jobs in J such that di₁ ≤ di₂ ≤ ......... ≤ di_k. Prove that J is a feasible solution if and only if the jobs in J can be processed in the order σ without violating any deadline.(7 marks) 3 (b) Using Prim's algorithm, determine minimum cost spanning tree for the weighted graph shown below, fig. Q3(b):

(7 marks) 3 (c) In the weighted diagram given below, fig. Q3(c) determine the shortest paths from vertex 1 to all other vertices.

(6 marks) 4 (a) Obtain the shortest paths from every vertex to every other vertex in the diagram given below: fig Q4(a)
(10 marks) 4 (b) Using Warshall's algorithm, obtain the transitive closure of the matrix given below: $$ R=\begin{pmatrix} 0 &1 &0 &0 \\0 &0 &0 &1 \\0 &0 &0 &0 \\ 1&0 &1 &0 \end{pmatrix} $$(10 marks) 5 (a) Show how insertion sort algorithm arranges the following members in increasing order.

(6 marks) 5 (b) Obtain topological sorting for the diagram given below:

(6 marks) 5 (c) Given algorithm for the following:
i) Comparison counting: ii) Distribution counting.(8 marks) 6 (a) Define the following: i) Tractable problems; ii) Class P; iii) Class NP; iv) Polynomial reduction; v) NP complete problems.(5 marks) 6 (b) State subset sum problem. Using back tracking, obtain a solution to the subset sum problem by taking s={6, 8, 2, 14} and d=16.(7 marks) 6 (c) Explain approximation algorithms for NP - hard problems in general. Also discuss approximation algorithms for knapsack problem.(8 marks) 7 (a) What is prefix computation problem? Give the algorithm for prefix computation which uses
i) n processors; ii) n/log n, processors. Obtain the time complexities of these algorithms.(10 marks) 7 (b) For an n×n matrix M with non negative integer coefficients, define M and give an algorithm for computing M. Prove that M can be computed from an n×n matrix M in 0(log n) time using n^3+∈ common CRCW PRAM processors for any fixed ∈>0.(10 marks)

Write short note on:

8 (a) Travelling salesperson problem.(5 marks) 8 (b) Input enhancement in string matching.(5 marks) 8 (c) Decision trees.(5 marks) 8 (d) Challenges of numerical algorithms.(5 marks)

ADD COMMENT EDIT