N2113113 · 60 marks · 2 hrs
Analysis of Algorithms
Exam: 21 Nov 2026 · 14:30-16:30 · Mumbai University, B.E. AI & DS Sem III (NEP-2020).
Units & topics
| Unit | Title & topics |
|---|---|
| Unit 1 | Introduction Recurrence solving, Selection Sort, Insertion Sort, Asymptotic notations, Big Theta (Θ) |
| Unit 2 | Divide and Conquer Approach Merge Sort (FIXED 10 MARKS), Binary Search, Divide and Conquer |
| Unit 3 | Greedy Method Approach Kruskal's MCST, Dijkstra's shortest path, Fractional Knapsack, Prim's MST, Greedy general method |
| Unit 4 | Dynamic Programming Approach Multistage Graph, LCS — Longest Common Subsequence, 0/1 Knapsack by DP, Floyd-Warshall, Principle of Optimality |
| Unit 5 | Backtracking and Branch and Bound Backtracking family, Graph Coloring, N-Queen Problem, 15-puzzle, Sum of Subset |
| Unit 6 | String Matching Algorithms KMP String Matching, Rabin-Karp, Naïve String Matching |
Question papers
Scanned originals as printed. Open a paper for preview, or download the PDF.
Dec 2025 · QP 99073
60 marks · 2 hrs · verified — scanned original
May 2026 · QP 14659
60 marks · 2 hrs · verified — scanned original
Most-asked topics
How many questions each topic got in Dec 2025 and May 2026. History, not a prediction — nothing here is guaranteed to appear next.
| Topic | Dec 2025 | May 2026 | Total | Marks |
|---|---|---|---|---|
| Backtracking family | 1 | 2 | 3 | 11 |
| Recurrence solving | 1 | 1 | 2 | 6 |
| Merge Sort (FIXED 10 MARKS) | 1 | 1 | 2 | 20 |
| Fractional Knapsack | 1 | 1 | 2 | 8 |
| Multistage Graph | 1 | 1 | 2 | 15 |
| LCS — Longest Common Subsequence | 1 | 1 | 2 | 13 |
| KMP String Matching | 0 | 2 | 2 | 8 |
| Selection Sort | 1 | 0 | 1 | 5 |
Question sets
Topic-wise question sets from the two papers — questions only.
AOA — Topic-wise Question Sets (Dec 2025 + May 2026)
6 pages · Scanned university question papers, grouped by topic · Questions only — no answers
All questions — Dec 2025 + May 2026
34 questions, quoted as printed. No answers are published on this site.
| Q | Topic | Question | Marks | Paper |
|---|---|---|---|---|
| Q1a | Recurrence solving | Find the complexity of given recurrence relation using Master Method: T(n) = 8T(n/2) + n². | 3 | aoa-dec2025 |
| Q1b | Binary Search | Write an algorithm for Binary Search. | 3 | aoa-dec2025 |
| Q1c | Greedy general method | Explain the general method of the Greedy Approach. | 3 | aoa-dec2025 |
| Q1d | Principle of Optimality | Explain the Principle of Optimality as applied to Dynamic Programming. | 3 | aoa-dec2025 |
| Q1e | Backtracking family | Differentiate between Backtracking and Branch & Bound techniques. | 3 | aoa-dec2025 |
| Q1f | Naïve String Matching | Explain the Naive String-Matching Algorithm. | 3 | aoa-dec2025 |
| Q2a | Selection Sort | Sort the following numbers using the Selection Sort, and show the array after each pass: 28, 17, 20, 75, 13, 15. | 5 | aoa-dec2025 |
| Q2b | Merge Sort (FIXED 10 MARKS) | Write an algorithm for Merge Sort. Derive its time complexity. Sort the following elements using Merge Sort: 32, 55, 17, 48, 64, 26. | 10 | aoa-dec2025 |
| Q3a | Big Theta (Θ) | Explain Big Theta (Θ) notation with a suitable example. | 5 | aoa-dec2025 |
| Q3b | Kruskal's MCST | 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: [graph: A–B 7, B–C 7, C–D 3, D–E 6, E–F 9, F–A 5, A–G 8, B–G 3, D–G 2, F–G 4]. | 10 | aoa-dec2025 |
| Q4a | Fractional Knapsack | Consider a Knapsack with capacity W = 16. There are six items with following weights and profits. (P1…P6) = (10, 5, 15, 7, 6, 18); (W1…W6) = (2, 3, 5, 7, 1, 4). Find the maximum profit using Fractional Knapsack algorithm. | 5 | aoa-dec2025 |
| Q4b | LCS — Longest Common Subsequence | 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 | aoa-dec2025 |
| Q5a | Multistage Graph | What is Multistage Graph? Explain Forward Approach method to find optimal path in Multistage Graph. | 5 | aoa-dec2025 |
| Q5b | N-Queen Problem | What is the N-Queen Problem? Design a backtracking algorithm to solve it. Provide step-by-step working of it using suitable example. | 10 | aoa-dec2025 |
| Q6a | Floyd-Warshall | Find the All-Pair Source Shortest path for all the vertices using Floyd-Warshall Algorithm: [directed graph: A→B 7, B→A 8, B→C −3, A→C 5, C→A 6]. | 5 | aoa-dec2025 |
| Q6b | Graph Coloring | Explain Graph Coloring method with suitable example. | 5 | aoa-dec2025 |
| Q6c | Rabin-Karp | Write Rabin Karp String Matching Algorithm. State its time complexity. | 5 | aoa-dec2025 |
| Q1a | Recurrence solving | Solve the following recurrence relation using recursion tree method: T(n) = 3T(n/3) + n². | 3 | aoa-may2026 |
| Q1b | Divide and Conquer | Explain Divide and Conquer strategy with diagram. | 3 | aoa-may2026 |
| Q1c | Fractional Knapsack | Differentiate between fractional and 0/1 knapsack problem (give minimum 5 relevant points). | 3 | aoa-may2026 |
| Q1d | LCS — Longest Common Subsequence | Find the LCS for the following sequences: X = ABCDE; Y = ACE. | 3 | aoa-may2026 |
| Q1e | Backtracking family | Explain the concept of Branch and Bound. | 3 | aoa-may2026 |
| Q1f | KMP String Matching | Explain the advantage of KMP algorithm over Naïve string matching algorithm. | 3 | aoa-may2026 |
| Q2a | Prim's MST | Find the Minimum spanning tree for the following graph using Prim's algorithm: [nodes 1–6; edges: 5–4: 9, 4–1: 1, 4–3: 5, 4–2: 3, 1–5: 4, 1–2: 2, 3–2: 3, 3–6: 8, 2–6: 7]. | 5 | aoa-may2026 |
| Q2b | Merge Sort (FIXED 10 MARKS) | Sort the following elements using Merge Sort and hence derive the complexity of Merge Sort: 34, 9, 56, 10, 78, 61, 98, 23, 38. | 10 | aoa-may2026 |
| Q3a | Insertion Sort | 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. | 5 | aoa-may2026 |
| Q3b | Dijkstra's shortest path | Find the shortest path for the following graph using Dijkstra's algorithm: (Source vertex is A). [graph: A–B 3, A–D 8, B–E 6, B–D 5, D–E 3, D–F 2, E–C 9, E–F 1, F–C 3]. | 10 | aoa-may2026 |
| Q4a | Backtracking family | Explain backtracking and how it is used to solve the graph coloring problem. | 5 | aoa-may2026 |
| Q4b | 0/1 Knapsack by DP | Solve the following knapsack problem using dynamic programming: (Capacity = 7). Table: I1: Weight 1, Profit 50; I2: Weight 2, Profit 40; I3: Weight 4, Profit 70; I4: Weight 5, Profit 80; I5: Weight 1, Profit 10. | 10 | aoa-may2026 |
| Q5a | 15-puzzle | Draw the partial state space tree for 15-puzzle problem. Specify the complexity of 15 puzzle problem. | 5 | aoa-may2026 |
| Q5b | Multistage Graph | Find the shortest distance from vertex 1 to vertex 12 for the following graph: [multistage graph: 1→2: 9, 1→3: 7, 1→4: 3, 1→5: 2; 2→6: 4, 2→7: 2; 3→6: 2, 3→7: 7; 4→8: 11; 5→8: 11, 5→7: 8; 6→9: 6, 6→10: 5; 7→9: 4, 7→10: 3; 8→10: 5, 8→11: 6; 9→12: 4; 10→12: 2; 11→12: 6]. | 10 | aoa-may2026 |
| Q6a | Asymptotic notations | Explain the different asymptotic notations with graphs. | 5 | aoa-may2026 |
| Q6b | KMP String Matching | Explain KMP String matching algorithm with example. | 5 | aoa-may2026 |
| Q6c | Sum of Subset | Solve the following sum of subset Problem: S = {3, 4, 5, 6} and sum = 9. | 5 | aoa-may2026 |