Visvesvaraya Technological University (VTU) 2006 B.E Computer Science ANALYSIS AND DESIGN OF ALGORITHMS - Question Paper

1 a. describe O notation, ? notation and ® notation
If f1(n) € O(g1(n)) and f2(n) € O(g2(n)), prove that
f1(n) + f2(n) € O(max [ g1(n), g2(n)]).
b. Develop an algorithm to determine the minimum and maximum values in an array a1,a2,.. ........an of integers (Here n>=1
and the entries in the array need not be distinct). Determine the worst case complexity function for this algorithm.
c. What is wrong with the subsequent argument?
Since n = O(n), 2n= O(n)..... we have

? Kn = ? O(n) =O(n^2)..
1<=k<= n 1<=k<= n


2 a. Design a brute force algorithm for computing the value of a polynomial
p(x) = Anx^n+An-1x^n-1+........+A1 x +A0
are provided point x0 and determine its worst case complexity class.
b. If the algorithm designed in part (a) is in ®(n^2). design a linear algorithm for this issue.
c. Write a quick sort algorithm.Derive worst-case and average-case complexities for this algorithm.


3 a. Write a reduce -by-one algorithm o generate all 2^n subsets of a set {a1, a2,........,an} in quashed order i.e. subset involving aj. can be listed
only after all subsets involving a1, a2,..........aj-1 (j=1,2........n-1)
b. Design a reduce -by- 1 algorithm for generating a gray code of order n.
c. Solve the system of linear equations provided beneath by gaussian elimination:
2x1 - x2 + x3 = 1
4x1 + x2 - x3 =5
x1 + x2 + x3 =0

4 a. describe 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 the increasing order? what about decreasig 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 various 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 comparisions needed to search for 1945 and 1543 in the table.


6 a. Write warshall's algorithm to obtain transitive closure of a diagraph. Prove that the time complexity of the algorithm is theta(n^3).
b. Apply warshall's algorithm to obtain transitive closure of a diagraph described by the subsequent adjacency matrix.

[ 0 0 0 0
0 0 one 1
0 one 0 0
one 0 one 0 ]


7 a. What is a decision tree? Use decision trees to establish lower bound on worst-case and avg. case efficiency of comparision based sorting
algorithm.
b. describe NP-complete issue. Prove that the hamiltonian circuit issue is polynomially reducible to the decision version of travelling salesman
issue. (TSF).

8 a. What is a C-approximation algorithm ? Write a 2- approximation algorithm for a TSP with a Euclidian distances.
b. If P ? NP . prove that there exists no C-approximation algorithm for TSP.

Earning:   Approval pending.