# VTU Previous Exam Papers BE CS 4th Semester

# 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 f_{2}(n) e 0(g_{2}(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_{)}a_{2}) 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) – a_{n}x^{n} + a_{n} ix^{n 1} -1-… + + a_{0} at a given point x_{Q} and determine its worst – case complexity class.

(b) If the algorithm designed in part (a) is in ®(ra^{2}), 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 2^{n} subsets of a set

{a_{1}} a_{2}5-*-}^{a}n} In quashed order i.e. subset involving a,j can be listed only after all subsets involving a_{2},

(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 ^{– x}z — 5

Xi + x_{2} + £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 (n^{3}) .

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