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

Design and Analysis of Algorithm

End Semester Examination, 2022-23
B. Tech - Semester : 05
Time : 03 hrs. - Max. Marks : 100

Instructions:

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

Section : A ( 4 x 10 = 40 Marks )

All questions are compulsory

1. What is the smallest value of n such that an algorithm whose running time is 100 n^2 runs faster than an algorithm whose running time is 2^n on the same machine?
2. Show the solution of the following recurrence relation using recursion tree method: T(n)=T(n/3)+T(2n/3)+ cn.
3. 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.
4. Prove the following:
   (a) 3^n= o(3^3n)
   (b) 10 n^2+7 = Ω(n)
5. Demonstrate the N-Queens problem in purview of NP Complete problems.
6. Identify the steps used in Dynamic programming approach while solving any problem? Discuss the 0/1 Knapsack problem with respect to Dynamic Programming. Is Greedy method equally applicable for the above problem?
7. Illustrate the notion of height balanced trees. Outline the properties of any one type height balanced trees.
8. Fractional Knapsack problem is solvable by Greedy approach optimally while 0-1 Knapsack problem may not be solved optimally by greedy approach. Interview this statement and give reasons in favor of your answer.
9. Explain the concept and applications of string matching.
10. Develop your understanding on P, NP, NPC, and NP Hard problems with an example of each.

Section : B ( 3 x 6 = 18 Marks )

All questions are compulsory

1. Examine the rules that all red black trees follow. Explain with the help of a suitable example.
   
   OR
   List and explain the characteristic properties associated with a problem that can be solved using dynamic programming.
2.  Discover the Longest Common Subsequence of <A, B, C, B, D, A, B> and  <B, D, C, A, B, A >.
   
   OR
   Examine an algorithm for the Quick Sort and illustrate the operation of the PARTITION on the array A = <2, 8, 7, 1, 3, 5, 6, 4>.
3. Examine what is Backtracking? Explain it with the help of 4-queens  problem.
   
   OR
   Distinguish between backtracking and branch & bound. Where each one of them is applicable?

Section : C ( 3 x 10 = 30 Marks )

All questions are compulsory

1. Find the value of the shortest distance from every node to every other node  in the following graph:
   
   

   
   
   OR
   Determine an optimal parenthesization of a matrix-chain product whose sequence of dimensions is <5, 10, 3, 12, 5, 50>.
   
2. Inspect the optimal solution of the following instance of 0/1 Knapsack:
   
   
   Knapsack Capacity W=10.
   
   OR
   Mark the steps involved in the insertion of following elements in an initially empty red black tree: 10, 18, 7, 15, 16, 30, 25.
   
   
3. Discover all the Valid Shifts using naive string-matching algorithm. Given:
   Text=1011101110 and Pattern =111.
   
   OR
   Working modulo q = 13, evaluate how many spurious hits does the Rabin-Karp matcher encounter in the Text T = 2359023141526739921 when looking for the pattern P = 31415.

Section : D ( 1 x 12 = 12 Marks )

All questions are compulsory

1. Perceive the Red Black Tree that results after successively inserting the keys 41, 38, 31, 12, 19, 8 into an initially empty red black tree.
   
   OR
   Formulate the notion of NP Complete and NP Hard Problems with examples. Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Organize P, Q, and R as cither NP-complete or NP-hard. Also give reasons in support of your answer.

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