VTU CSE 4th Semester Analysis and Design of Algorithms Question Paper February 2006: To score better marks in the 4th semester, you should have depth knowledge in every subject. You can boost your preparation by solving previous year question papers. Every semester has an important role to shape the Computer Science & Engineering Career. It will give you information about the important chapters and concepts to be covered in all chapters.

Here we are providing you the complete guide on VTU CSE 4th Semester Analysis and Design of Algorithms Question Paper February 2006.

## VTU CSE 4th Semester Analysis and Design of Algorithms Question Paper February 2006

You must have Analysis and Design of Algorithms Question Paper along with the latest Computer Science 4th sem Syllabus to enhance your semester exam preparation.

Here you can check the VTU CSE 4th Semester Analysis and Design of Algorithms Question Paper 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 |

We have covered VTU CSE 4th Semester Analysis and Design of Algorithms Question Paper February 2006. Feel free to ask us any questions in the comment section below.