## 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_{1}(n) ∈ 0 (g_{1} (n)) and t_{2} (n) ∈ 0 (g_{2} (n)), prove that t_{1} (n)+ t_{2} (n) ∈ 0 (max {g_{1} (n), g_{2} (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 | 91 | 84 | 63 | 42 |

**3 (a)**Let J be a set of K jobs and σ= i

_{1}, i

_{2}, i

_{3},........, i

_{k}be a permutation of jobs in J such that di

_{1}≤ di

_{2}≤ ......... ≤ 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.

61 | 28 | 9 | 85 | 34 |

**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)