Mumbai University Solved Question Papers
Analysis of Algorithm
Previous Year Question Paper with Solution
Engineering · Sem 3
May 2026 Examination
munotes.in
Mumbai
Engineering Sem 3 Analysis of Algorithm May 2026 Question Paper with Solutions
Get access to whole semester resourcesSemester Pass
First published on munotes.in on 5 November 2026.
Published by munotes.in, Mumbai.
Model answers written and edited by the munotes.in editorial desk.
Passages from this volume may be quoted, in print, online or by an AI system, with credit: name munotes.in and link to this volume's page. The volume may not be reproduced as a whole. Full terms at munotes.in/content-license.
munotes.in is an independent study resource for students of the University of Mumbai. It is not affiliated with the University of Mumbai, and is not endorsed by it.
The University does not publish an official answer key for this paper. The answers in this volume are model answers, written to show how a full-mark answer is built. They are a study aid, not an authority on what an examiner marked.
The question paper reproduced here is the paper as set by the University of Mumbai at the May 2026 examination.
Contents
The questions below are the paper as the University of Mumbai set it at the May 2026 examination, in the order it was set.
MarksPage
MarksPage
The Paper as Set
The questions in this volume are the questions asked at the May 2026 examination, reproduced as the University of Mumbai set them, in the order it set them. Nothing has been reworded, added or left out. Only the answers are ours. See the original question paper.
Duration 2 hours · Total marks 60 · 17 questions answered
Instructions printed on the 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.
How to use this volume
Solve the paper first, under exam conditions and against the clock. Then read the answers here and mark your own. Reading a solution before attempting the question feels productive and teaches very little, because recognising an answer is not the same as being able to write one.
Q1
Q1)
Answer the following, Any Five · 15 Marks
a)Solve the following recurrence relation using recursion tree method: T(n) = 3T(n/3) + n².[3]
Answer
For full marks, cover: the tree level by level, the cost of each level, the height and the number of leaves, the sum as a geometric series, and the bound Θ(n²).
Building the tree
The root costs n². It has 3 children, each a problem of size n/3.
- Level 0: one node of cost n². Level cost n².
- Level 1: three nodes, each (n/3)² = n²/9. Level cost 3 × n²/9 = n²/3.
- Level 2: nine nodes, each (n/9)² = n²/81. Level cost 9 × n²/81 = n²/9.
- Level i: 3ⁱ nodes, each (n/3ⁱ)². Level cost n²/3ⁱ.
Height and leaves
The size reaches 1 when n/3ⁱ = 1, that is at i = log₃ n. So the tree has log₃ n + 1 levels. The last level has 3^(log₃ n) = n leaves, each costing T(1), so the leaves cost Θ(n).
The sum
T(n) = n²(1 + 1/3 + 1/9 + ...) + Θ(n).
The bracket is a decreasing geometric series with ratio 1/3. Even taken to infinity it adds to 1/(1 - 1/3) = 3/2. So T(n) <= (3/2)n² + Θ(n).
Also T(n) >= n², the cost of the root alone.
The bound
The root dominates, because each level costs one third of the level above. Hence T(n) = Θ(n²). The master theorem agrees: a = 3, b = 3, n^(log₃ 3) = n, and f(n) = n² grows faster, so case 3 gives Θ(n²).
Conclusion. The level costs are n², n²/3, n²/9 and so on, a geometric series bounded by (3/2)n², plus Θ(n) for the n leaves. So T(n) = Θ(n²).
The rest of the answers
The first answer is free. The rest come with the B.E. (Computer Engineering) Semester 3 solved papers.
You have read the question paper and its first answer in full. Buy the solved papers once and you can read every answer of every solved paper in this semester.
Solved papers: ₹499 Already bought it? Sign in
The question paper itself stays free, and so does the syllabus.
Found an error in this volume? Report it and we will check it against the paper.