Q.1
14 Marks(a)
Find Omega (Ω) notation of function f(n)=2n2 + n * lg n + 6n
(b)
Define Big-oh and Theta notations with graph
(c)
Write and analyze an insertion sort algorithm to sort n items into ascending order.
Also asked in Winter 2024 Q1c
Gujarat Technological UniversitySummer 2024 examination
GTU 3150703 Analysis and Design of Algorithms (ADA) Summer 2024 Question Paper & PDF
B.E. · Computer Engineering · Semester 5 · Subject code 3150703
- Total
- 70 marks
- To pass
- 23 marks (33%)
- Duration
- 2.5 Hours 2:30 PM – 5:00 PM
- Questions
- 5 with internal choice
No solutions on this paper yetNeed them for your exam? Ask once. Papers that students ask for are solved first, and we aim to add them within 24 hours.
Noted. This paper is in our queue now. Check back tomorrow.
We could not record that here. Email the paper name to hirenjsca@gmail.com and we will add it.
9 of 25 questions on this paper were also asked in other years. 8 more are types of question GTU sets again with new data. Each is marked below with the years it appeared.See all 39 repeated 3150703 questions, most asked first
Q.2
14 Marks(a)
Explain: Articulation Point, Graph, Tree
(b)
Solve following recurrence using Master Theorem:
T(n) = 3T(n/3) + n^3.
Also asked in Summer 2026 Q2b, Winter 2024 Q2c, Winter 2023 Q1b
(c)
Illustrate the working of the quick sort on input instance: 25, 29, 30, 35, 42, 47, 50, 52, 60. Comment on the nature of input i.e. best case, average case or worst case.
Also asked in Winter 2023 Q2c
OR
(c)
What is recurrence? Explain recursion-tree method with suitable example.
Q.3
14 Marks(a)
What is Principle of Optimality? Explain its use in Dynamic Programming Method
Also asked in Summer 2026 Q3a, Winter 2025 Q3a, Summer 2025 Q4a, Winter 2024 Q4b OR, Summer 2023 Q3a
(b)
Explain Binomial Coefficient algorithm using dynamic programming.
Also asked in Winter 2023 Q4a OR
(c)
Obtain longest common subsequence using dynamic programming. Given A = “acabaca” and B = “bacac”.
Also asked in Summer 2026 Q3c OR, Winter 2025 Q3c OR, Summer 2025 Q4c OR
OR
(b)
Demonstrate Binary Search method to search Key = 14, form the array A=<2,4,7,8,9,10,12,14,18>
Also asked in Winter 2023 Q5a
(c)
What is a minimum spanning tree? Draw the minimum spanning tree correspond to following graph using Prim’s algorithm.
Also asked in Winter 2025 Q4c, Winter 2024 Q4c, Summer 2023 Q4c
Q.4
14 Marks(a)
Explain Tower of Hanoi Problem, Derive its recursion equation and computer it’s time complexity.
(b)
Using greedy algorithm find an optimal schedule for following jobs with n=7 profits: (P1, P2, P3, P4, P5, P6, P7) = (3, 5, 18, 20, 6, 1, 38) and deadline (d1, d2, d3, d4, d5, d6, d7) = (1, 3, 3, 4, 1, 2, 1)
(c)
Solve the following Knapsack Problem using greedy method. Number of items = 5, knapsack capacity W = 100, weight vector = {50, 40, 30, 20, 10} and profit vector = {1, 2, 3, 4, 5}.
Also asked in Winter 2023 Q5b
OR
(a)
What are the disadvantages of greedy method over dynamic programming method?
Also asked in Summer 2023 Q3b OR
(b)
Find an optimal Huffman code for the following set of frequency. A : 50, b: 20, c:
15, d: 30
Also asked in Summer 2026 Q3b, Winter 2025 Q4b OR, Winter 2023 Q3b OR, Summer 2023 Q4a
(c)
Consider a Knapsack with the maximum weight capacity M is 7, for the objects with value [12,10,20,15] with weights [2,1,3,2] solve using dynamic programming the maximum value the knapsack can have.
Also asked in Winter 2025 Q3c, Winter 2023 Q3c OR, Summer 2023 Q3c OR
Q.5
14 Marks(a)
Define NP-Complete and NP-Hard problems.
(b)
Draw the state space tree Diagram for 4 Queens problem.
Also asked in Winter 2025 Q5c, Summer 2025 Q5b, Winter 2024 Q5a OR, Winter 2023 Q4c OR
(c)
Find all pair of shortest path using Floyd’s Algorithm for following graph.
OR
(b)
Explain the naive string matching algorithm.
Also asked in Winter 2025 Q5a, Summer 2025 Q5c, Summer 2023 Q5b
(c)
Explain spurious hits in Rabin-Karp string matching algorithm with example.
Working modulo q=13, how many spurious hits does the Rabin Karp matcher encounter in the text T = 2359023141526739921 when looking for the pattern P = 31415?
Also asked in Summer 2026 Q5b, Winter 2025 Q5c OR, Winter 2023 Q5c OR, Summer 2023 Q5a
More Analysis and Design of Algorithms papers
Questions repeat across sessions. Working through two or three papers shows you which topics GTU asks most.
Other Semester 5 subjects
BE Computer
Preparing with friends?
Send this paper to your class group. Every question has its own link.
About this paper
Official Gujarat Technological University (GTU) examination paper for Analysis and Design of Algorithms (ADA) (Summer 2024, B.E. · Computer Engineering, Sem 5). Features complete 70-mark regular & remedial examination pattern, official marking distribution across all 5 questions, and direct 1-click official PDF download.
Transcribed for student exam preparation from Gujarat Technological University official examination archives. Questions, syllabus guidelines, and curriculum marking schemes remain the intellectual property of Gujarat Technological University.