Design and Analysis of Algorithm : Mid Sem Examination ( 5th Sem )

Design and Analysis of Algorithm

Mid Semester Examination, 2022-23
B. Tech - Semester : 05
Time : 1.30 hrs. - Max. Marks : 40

Instructions:

1. All questions are Compulsory
2. Assume missing data suitably, if any.

Section : A ( 2 x 2 = 4 Marks )

All questions are compulsory

1. What is the smallest value of n such that an algorithm whose running time is 100n² runs faster then an algorithm whose running time is 2ⁿ on the same machine?
2. Is 2ⁿ⁺¹ = O(2ⁿ)?

Section : B ( 4 x 2 = 8 Marks )

All questions are compulsory

1. Why do you use asymptotic notation in the study of algorithms? Explain in brief various asymptotic notations and their significance.
2. Solve the following recurrence relation by iteration:
   T(n) = T(n-1) + n⁴

Section : C ( 6 x 2 = 12 Marks )

All questions are compulsory

1. Let f(n) and g(n) be asymptotically non-negative functions. Use the basic definition of 𑁜 notation prove that Max (f(n), g(n)) = 𑁜(f(n) + g(n)).
   
   OR
   Prove that if f1(n) = O(g1(n)) and f2(n) = O(g2(n)), then
    f1(n) +  f2(n) = O(g1(n) + g2(n)).
2. There are 5 jobs whose penalties (p1,p2,p3,p4,p5) are (20,15,10,5,1) and deadlines (d1,d2,d3,d4,d5) are (2,2,1,3,3). Find the optimal solution that minimizes the penalty on scheduling these jobs.
   
   OR
   What is Backtracking? Explain it with the help of 4-queens problem.

Section : D ( 8 x 2 = 16 Marks )

All questions are compulsory

1. Write an algorithm for the quick sort and show how the partitioning algorithm of quick sort will place 99 in its correct position. Show all the steps clearly.
   106 117 128 134 141 91 84 63 99.
   
   OR
   Illustrate the operation of the counting sort on the following array:
   A = [ 6,0,2,0,1,3,4,6,1,3,2 ].
2. Write the Dijkastra's algorithm for finding the shortest path from a single source. What is its complexity? Also find the shortest paths in the following graph assuming that "1" is the source node.
   
   
   
   
   OR
   

   Build a heap for the array A = 5,13,2,25,7,17,20,8,4 and illustrate the operation of the heap sort in this array.

*******************