# Analysis and Design of Algorithms February 2006

Note: Answer any FIVE full questions.

1 (a) Define ; O – notation , ft – notation and ©notation.

If fi(n) 6 0(ffi(rc)) and f2(n) e 0(g2(n)) , prove that fl(n) + h(n) 6 0(max[Sl(n), gj-(n)J).

(b) Develop an algorithm to determine the minimum and maximum values in an array ai)a2)       yan of integers (Here n > 1 and the entries in the array need not be distinct). Determine worst-case complexity function for this algorithm.

(c) What is wrong with the foliowing argument ?

Since n = O(n), 2n – O(rc),… we have

2  (a) Design a brute-force algorithm for computing the value of a polynomial

p(x) – anxn + an ixn 1 -1-… + + a0 at a given point xQ and determine its worst – case complexity class.

(b) If the algorithm designed in part (a) is in ®(ra2), design a linear algorithm for this problem.

(c) Write quick sort algorithm. Derive worst – case and average – case complexities for this algorithm.

3.  (a) Write a decrease – by – one algorithm to generate all 2n subsets of a set

{a1} a25-*-}an} In quashed order i.e. subset involving a,j can be listed only af­ter all subsets involving a2,

(b) Design a decrease – by – one algorithm for generating a gray code of order n.

(c)      Solve the system of linear equations given below by Gaussian elimination :

2xi – X2 + £3 — 1

4a?! + a?2 – xz — 5

Xi + x2 + £3 = 0

4. (a) Define a heap. Prove that a n-element heap has height [log n]. Show that there is a linear algorithm to construct a heap of size n.

(b) What is the running time of heapsort on an array A of length n that is already sorted in increasing order ? What about decreasing order ?)

5. (a) What is input enhancement ? Apply this technique to design a linear sorting algorithm.

(b)When does collision occur in hashing ? What are different mechanisms used to resolve collisions ?

(C)Consider open hashing with linear probing policy. For the input;

1055, 1492, 1776, 1812, 1918, 1945 inserted in the order and hash function : h(k) = 5k(mod 8)

i)      Construct the open hash table

ii)   Show the sequence of key comparisons needed to search for 1945 and 1543 in the table.

6 (a) Write Warshall’s algorithm to find transitive closure of a digraph. Prove that the time complexity of the algorithm is (n3) .

(B) Apply Warshall’s algorithm to find transitive closure of the digraph defined by the following adjacency matrix,

7 (a)What is a decision tree ? Use decision trees to establish lower bound on worst-case and average – case efficiency of comparison based sorting algorithm.

(b)Define NP – complete problem. Prove that the Hamiltonion circuit problem is polynomially reducible to the decision version of traveling salesman problem.

8 (a)What is a C – approximation algorithm ? Write a 2 – approximation algorithm for TSP with Euclidian distances.

(b) If p £ NP. Prove that there exists no C – approximation algorithm for TSP.

 0 0 0 0 0 0 1 1 0 1 0 0 1 0 1 0