Computer Engineering Sem 4 Analysis of Algorithm Question Paper PDF 2026 - Mumbai University | munotes

Questions asked in this paper

• (3) Figures to the right indicate full marks

1. Q1 Attempt any four
   • (A) Describe the relationship along P, NP, NP-hard, NP-complete? 5
   • (B) What is the difference between divide and conquer approach and dynamic
   • (C) Explain Multistage graph with example. 5
   • (D) Write an abstract algorithm for greedy design method. 5
   • (E) What is Asymptotic analysis and define big Oh, big Omega and Theta notation? 5
2. Q2 (A) Sort the following numbers using Quick Sort. Also, derive the time complexity of Quick
   • (B) What is Knuth Morris Pratt Method of Pattern Matching? Give Examples. 10
3. Q3 (A) Solve the following instance of Job sequencing with deadlines problem n=7, profits (p1, (1,3,4, 3,2, 1,2). Schedule the jobs in such way so as to get maximum profit. 10
   • (B) Write and explain sum of subset algorithm =5,W 10
4. Q4 (A) Find Longest Common Subsequence for following strings 10 marks
   • (B) Write an algorithm to find the minimum and maximum value using divide and conquer and also derive its complexity. 10 Paper Subject Code: 40522 Analysis of Algorithm
5. Q5 (A) Find a minimum cost path from 3 to 2 in the given graph using dynamic
   • (B) Write an algorithm to solve N Queens problem. Show its working for N 10
6. Q6 Attempt any two 20 marks
   • (A) Explain naive string matching algorithm with example
   • (B) Explain 0/1 knapsack problem using dynamic programming
   • (C) To Find MST of following graph using prim’s and kruskal’s Algorithm

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