Question 1
(a)
Find Omega (Ω) notation of function f(n)=2n2 + n * lg n + 6n
3 Marks
(b)
Define Big-oh and Theta notations with graph
4 Marks
(c)
Write and analyze an insertion sort algorithm to sort n items into ascending order.
7 Marks
Gujarat Technological UniversitySummer 2024 Examination
GTU 3150703 Analysis and Design of Algorithms (ADA) Summer 2024 Paper Solution & PDF
B.E. · Computer Engineering · Semester 5 · Subject Code: 3150703
Total Marks70 MarksExternal theory exam
Passing Marks23 Marks33% minimum cutoff
Exam Duration2.5 Hours2:30 PM – 5:00 PM
Paper Structure5 QuestionsWith internal OR choices
Question 2
(a)
Explain: Articulation Point, Graph, Tree
3 Marks
(b)
Solve following recurrence using Master Theorem:
T(n) = 3T(n/3) + n^3.
4 Marks
(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.
7 Marks
OR OPTION
(c)
What is recurrence? Explain recursion-tree method with suitable example.
7 Marks
Question 3
(a)
What is Principle of Optimality? Explain its use in Dynamic Programming Method
3 Marks
(b)
Explain Binomial Coefficient algorithm using dynamic programming.
4 Marks
(c)
Obtain longest common subsequence using dynamic programming. Given A = “acabaca” and B = “bacac”.
7 Marks
OR OPTION
(a)
Explain the steps of greedy strategy for solving a problem
3 Marks
(b)
Demonstrate Binary Search method to search Key = 14, form the array A=<2,4,7,8,9,10,12,14,18>
4 Marks
(c)
What is a minimum spanning tree? Draw the minimum spanning tree correspond to following graph using Prim’s algorithm.
7 Marks
Question 4
(a)
Explain Tower of Hanoi Problem, Derive its recursion equation and computer it’s time complexity.
3 Marks
(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)
4 Marks
(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}.
7 Marks
OR OPTION
(a)
What are the disadvantages of greedy method over dynamic programming method?
3 Marks
(b)
Find an optimal Huffman code for the following set of frequency. A : 50, b: 20, c:
15, d: 30
4 Marks
(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.
7 Marks
Question 5
(a)
Define NP-Complete and NP-Hard problems.
3 Marks
(b)
Draw the state space tree Diagram for 4 Queens problem.
4 Marks
(c)
Find all pair of shortest path using Floyd’s Algorithm for following graph.
7 Marks
OR OPTION
(a)
Define BFS. How it is differ from DFS.
3 Marks
(b)
Explain the naive string matching algorithm.
4 Marks
(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?
7 Marks
College Exam Groups
Studying for Analysis and Design of Algorithms?
Circulate this solved paper with KaTeX formulas and 1-click AI step solvers to your batchmates on WhatsApp or Telegram.
About this Examination Paper & Attribution
Official Gujarat Technological University (GTU) examination paper and step-by-step solutions 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.