# Design and Analysis of Algorithms June 2012

Note: Answer FIVE full questions, selecting at least TWO questions from each part.

PART -A

1 (a)  If 11(n) e 0 (gi (n)) and t2 (n) e 0(g2 (n)), prove that

ti(n) + t2(n) e 0(max {gi(n), g2(n)}).

(b) If M(n) denotes the number of moves in tower of Hanoi puzzle when n disks are involved,give a recurrence relation for M(n) and solve this recurrence relation.

(C) Give an algorithm for selection sort. If C(n) denotes the number of times the algorithm isexecuted (n denotes input size), obtain an expression for C(n).

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(l) = 0.

(b) If ne[2k‘’, 2k), 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. (06 Marks) Give an algorithm for merge sort.

(C) 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 a = ii, i2, i3,   , ik be a permutation of jobs in J such that dii < di2 < dik. Prove that J is a feasible solution if and only if the jobs in J can be processed in the order a without violating any deadline………….

(b) Using Prim’s algorithm, determine minimum cost spanning tree for the weighted graph shown below, (C) In the weighted digraph given below, fig.Q.3(c) determine the shortest paths from vertex 1 to all other vertices. Fig.Q.3(c)

4 (a) Obtain the shortest paths from every vertex to every other vertex in the diagraph given below; fig.Q.4(a) (B)Using Warshall’s algorithm, obtain the transitive closure of the matrix given below:

R =0 1            0 0

0 0          0 1

0 0          0 0

10            10

PART-B

5 (a)Show how insertion sort algorithm arranges the following members in increasing order. 61   28  9  85  34.

(b) Obtain topological sorting for the diagraph given below: (C).Give algorithms for the following:  i) Comparison counting;  ii) Distribution counting.

6. Define the following: i) Tractable problems; ii) Class P; iii) Class NP; iv) Polynomial reduction; v) NP complete problems.

(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.

(c) Explain approximation algorithms for NP – hard problems in general. Also discuss approximation algorithms for knapsack problem.

7 (a) What is prefix computation problem? Give the algorithms for prefix computation which uses n

i) n processors; ii) log n processors. Obtain the time complexities of these algorithms.

(b) For an n x n matrix M with nonnegative integer coefficients, define M and give an algorithm for computing M . Prove that M can be computed from an n x n matrix M in 0(log n) time using n common CRCW PRAM processors for any fixed e > 0.

8 Write short notes on:

(a)  Traveling salesperson problem.

(b) Input enhancement in string matching.

(c)  Decision trees.

(d) Challenges of numerical algorithms.