Engineering B.E. (Computer Engineering) Sem 3 Analysis of Algorithm May 2026 Question Paper - Mumbai University | munotes

Questions asked in this paper

• N.B. (1) Question No. 1 is Compulsory. (2) Attempt any THREE questions out of the remaining FIVE. (3) All questions carry equal marks. (4) Figures to the right indicate full marks.

Q1 Q1) (Answer the following, Any Five) 15 Marks

1. a) Solve the following recurrence relation using recursion tree method: T(n) = 3T(n/3) + n².
   Read the model answer
2. b) Explain Divide and Conquer strategy with diagram.
   Read the model answer
3. c) Differentiate between fractional and 0/1 knapsack problem (give minimum 5 relevant points).
   Read the model answer
4. d) Find the LCS for the following sequences: X = ABCDE, Y = ACE.
   Read the model answer
5. e) Explain the concept of Branch and Bound.
   Read the model answer
6. f) Explain the advantage of KMP algorithm over Naïve string matching algorithm.
   Read the model answer

Q2 Q2) 15 Marks

1. a) Find the Minimum spanning tree for the following graph using Prim's algorithm. The graph has vertices 1 to 6 and the edges (5, 4) = 9, (5, 1) = 4, (4, 1) = 1, (4, 3) = 5, (4, 2) = 3, (3, 2) = 3, (3, 6) = 8, (2, 6) = 7, (1, 2) = 2.
   Read the model answer
2. b) Sort the following elements using Merge Sort and hence derive the complexity of Merge Sort: 34, 9, 56, 10, 78, 61, 98, 23, 38.
   Read the model answer

Q3 Q3) 15 Marks

1. a) Sort the following elements using insertion sort: 90, 1, 4, 2, 78, 45, 39, 58, 79. Show output after each pass. Also, derive complexity of insertion sort.
   Read the model answer
2. b) Find the shortest path for the following graph using Dijkstra's algorithm (Source vertex is A). The graph has vertices A to F and the edges A-B = 3, A-D = 8, B-D = 5, B-E = 6, D-E = 3, D-F = 2, E-F = 1, E-C = 9, F-C = 3.
   Read the model answer

Q4 Q4) 15 Marks

1. a) Explain backtracking and how it is used to solve the graph coloring problem.
   Read the model answer
2. b) Solve the following knapsack problem using dynamic programming (Capacity = 7): Item: I1, I2, I3, I4, I5; Weight: 1, 2, 4, 5, 1; Profit: 50, 40, 70, 80, 10.
   Read the model answer

Q5 Q5) 15 Marks

1. a) Draw the partial state space tree for 15-puzzle problem. Specify the complexity of 15 puzzle problem.
   Read the model answer
2. b) Find the shortest distance from vertex 1 to vertex 12 for the following graph. The directed graph has the edges 1 to 2 = 9, 1 to 3 = 7, 1 to 4 = 3, 1 to 5 = 2, 2 to 6 = 4, 2 to 7 = 2, 2 to 8 = 1, 3 to 6 = 2, 3 to 7 = 7, 4 to 8 = 11, 5 to 7 = 11, 5 to 8 = 8, 6 to 9 = 6, 6 to 10 = 5, 7 to 9 = 4, 7 to 10 = 3, 8 to 10 = 5, 8 to 11 = 6, 9 to 12 = 4, 10 to 12 = 2, 11 to 12 = 6.
   Read the model answer

Q6 Q6) 15 Marks

1. a) Explain the different asymptotic notations with graphs.
   Read the model answer
2. b) Explain KMP String matching algorithm with example.
   Read the model answer
3. c) Solve the following sum of subset Problem: S = {3, 4, 5, 6} and sum = 9.
   Read the model answer

Read from the scan above, so a character or two may differ. The scan is the original.