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

Questions asked in this paper

• Note: (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) Find the complexity of given recurrence relation using Master Method: T(n) = 8T(n/2) + n². 3 marks
   Read the model answer
2. b) Write an algorithm for Binary Search. 3 marks
   Read the model answer
3. c) Explain the general method of the Greedy Approach. 3 marks
   Read the model answer
4. d) Explain the Principle of Optimality as applied to Dynamic Programming. 3 marks
   Read the model answer
5. e) Differentiate between Backtracking and Branch & Bound techniques. 3 marks
   Read the model answer
6. f) Explain the Naive String-Matching Algorithm. 3 marks
   Read the model answer

Q2 Q2 15 Marks

1. a) Sort the following numbers using the Selection Sort, and show the array after each pass: 28, 17, 20, 75, 13, 15. 5 marks
   Read the model answer
2. b) Write an algorithm for Merge Sort. Derive its time complexity. Sort the following elements using Merge Sort: 32, 55, 17, 48, 64, 26. 10 marks
   Read the model answer

Q3 Q3 15 Marks

1. a) Explain Big Theta (Θ) notation with a suitable example. 5 marks
   Read the model answer
2. b) What is Minimum Cost Spanning Tree? Write Kruskal's algorithm and state its time complexity. Find Minimum Cost Spanning Tree for following graph using Kruskal's Algorithm. [Figure: an undirected weighted graph on the vertices A, B, C, D, E, F, G with the edges A-B 1, B-C 7, B-G 3, C-G 2, C-D 3, A-G 8, A-F 5, G-E 4, D-E 6 and F-E 9.] 10 marks
   Read the model answer

Q4 Q4 15 Marks

1. a) Consider a Knapsack with capacity W = 16. There are six items with following weights and profits. (P1, P2, P3, P4, P5, P6) = (10, 5, 15, 7, 6, 18); (W1, W2, W3, W4, W5, W6) = (2, 3, 5, 7, 1, 4). Find the maximum profit using Fractional Knapsack algorithm. 5 marks
   Read the model answer
2. b) Write an algorithm to find Longest Common Subsequences between two given strings. Derive its time complexity. Find the LCS between following strings: X = AVANTIKA, Y = KARNAVATI. 10 marks
   Read the model answer

Q5 Q5 15 Marks

1. a) What is Multistage Graph? Explain Forward Approach method to find optimal path in Multistage Graph. 5 marks
   Read the model answer
2. b) What is the N-Queen Problem? Design a backtracking algorithm to solve it. Provide step-by-step working of it using suitable example. 10 marks
   Read the model answer

Q6 Q6 15 Marks

1. a) Find the All-Pair Source Shortest path for all the vertices using Floyd-Warshall Algorithm. [Figure: a directed weighted graph on the vertices A, B, C with the edges A to B 7, B to A 8, A to C 5, C to A 6 and B to C -3.] 5 marks
   Read the model answer
2. b) Explain Graph Coloring method with suitable example. 5 marks
   Read the model answer
3. c) Write Rabin Karp String Matching Algorithm. State its time complexity. 5 marks
   Read the model answer

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