Design and Analysis of Algorithms - Dec 2012

Computer Science Engg. (Semester 4)

TOTAL MARKS: 100
TOTAL TIME: 3 HOURS (1) Question 1 is compulsory.
(2) Attempt any four from the remaining questions.
(3) Assume data wherever required.
(4) Figures to the right indicate full marks. 1 (a) Define asymptotic notations.(3 marks) 1 (b) Algorithm X(int N)
{
{
int P;
for i? 1 to N
{
printf(" %d \t * \t %d=%d", N, i, P);
P-P+N;
}
}
i) What does this algorithm compute?
ii) What is the basic operation?

iii) How many times the basic operation is executed?
iv) What is the efficiency class of this algorithm?(4 marks) 1 (c) Solve the following recurrence relation $$ \ f(n)= \left\{\begin{matrix} f(n-1) &n> 0 \\ 0 & n=0 \end{matrix}\right. $$ $$ \begin{matrix}x(n)=3x(n-1) &for \ n>1, \ x(1)=4 \\x(n) =x(n|2)+n &for \ n>1,\ x(1) =1 n=2^k\end{matrix} $$(4 marks) 1 (d) Sort the list EXAMPLE by dubbed sort, ls there any possibilities that bubble sort can be stopped earlier?(5 marks) 2 (a) Discuss how quick sort work to sort an array. Trace quick sort algorithm for the following data set 65, 70, 75, 80, 85, 60, 55, 50, 45. Also derive the worst case complexity of quick sort.(9 marks) 2 (b) Write the recursive algorithm for merge sort.(4 marks) 2 (c) Consider the following set of 14 elements in an array list, -15, -6, 0, 7, 9, 23, 54, 82, 101, 112, 125, 131, 142, 151 when binary search is applied on these elements, find the elements which required maximum number of comparisons. Also determine average number of key comparison for successful search and unsuccessful search.(4 marks) 2 (d) Derive the time complexity for defective chess board.(3 marks) 3 (a) Solve the following instance of knapsack problem, using greedy algorithm

3 (b) Using Prim's algorithm, determine minimum cost spanning tree for the following graph Fig Q3(b)
How Knapsack and Prim's algorithms guarantee the elimination of cycles?
  (7 marks)

3 (c) In the above graph fig. Q3(c), determine the shortest distances from source vertex 5 to all the remaining vertices, using Dijkstra's algorithm.
  (8 marks)

4 (c) Generate the transitive closure of the graph is given below.

 

(7 marks)