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 M

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 M

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 M

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 M

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 M

2(c)
Give an algorithm for merge sort.

5 M

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 |

4 M

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 M

3 (b)
Using Prim's algorithm, determine minimum cost spanning tree for the weighted graph shown below, fig. Q3(b):

7 M

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

6 M

4 (a)
Obtain the shortest paths from every vertex to every other vertex in the diagram given below: fig Q4(a)

10 M

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 M

5 (a)
Show how insertion sort algorithm arranges the following members in increasing order.

61 | 28 | 9 | 85 | 34 |

6 M

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

6 M

5 (c)
Given algorithm for the following:

i) Comparison counting: ii) Distribution counting.

i) Comparison counting: ii) Distribution counting.

8 M

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

5 M

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 M

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

8 M

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.

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

10 M

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 M

Write short note on:

8 (a)
Travelling salesperson problem.

5 M

8 (b)
Input enhancement in string matching.

5 M

8 (c)
Decision trees.

5 M

8 (d)
Challenges of numerical algorithms.

5 M

More question papers from Design and Analysis of Algorithms