VTU Previous Exam Papers BE CS 4th Sem Analysis and Design of Algorithms February 2006

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

Leave a Comment