Question 1
(a)
Define domain, co-domain, and range of a function.
3 Marks
(b)
Explain the amortized analysis technique with an example.
4 Marks
(c)
Derive the time complexity of Heap Sort step by step with suitable justification.
7 Marks
Gujarat Technological UniversitySummer 2026 Examination
GTU 3150703 Analysis and Design of Algorithms (ADA) Summer 2026 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)
Perform Counting Sort on the input array A = [4, 2, 2, 8, 3, 3, 1]. Show all steps counting array, cumulative count, and the final sorted output.
3 Marks
(b)
Solve the recurrence relation T(n) = 2T(n/2) + n using the Master Theorem.
4 Marks
(c)
Derive the recurrence relation and solve it for Merge Sort using the Master Theorem.
7 Marks
OR OPTION
(c)
Describe the Multiplying Large Integers Problem using Divide and Conquer.
7 Marks
Question 3
(a)
Explain the Principle of Optimality in Dynamic Programming with a suitable example.
3 Marks
(b)
Explain the Huffman Coding algorithm with a suitable example and construct the Huffman Tree.
4 Marks
(c)
Solve the 0/1 Knapsack problem using dynamic programming for the given data:
Weights = [2, 3, 4, 5], Values = [3, 4, 5, 6], Capacity = 5.
7 Marks
OR OPTION
(a)
State and explain the basic characteristics of problems that can be solved using Dynamic Programming.
3 Marks
(b)
Describe the Knapsack Problem and mention why the Greedy approach works for the fractional version but not for the 0/1 version.
4 Marks
(c)
For the two strings X = AGGTAB and Y = GXTXAYB, find the Longest Common Sub-sequence using Dynamic Programming.
7 Marks
Question 4
(a)
Explain the basic concepts of graphs with suitable examples. Differentiate between directed and undirected graphs.
3 Marks
(b)
Perform Depth First Search (DFS) starting from vertex A for the graph:
Vertices: A, B, C, D, E Edges: (A, B), (A, C), (B, D), (C, D), (D, E). Write the order of traversal.
4 Marks
(c)
Find the Minimum Spanning Tree using Kruskal’s algorithm for the following graph:
Vertices = {A, B, C, D, E} Edges with weights: A-B: 2, A-C: 3, B-C: 1, B-D: 4, C-E: 5, D-E: 2.
7 Marks
OR OPTION
(a)
Explain the Breadth First Search (BFS) algorithm. Illustrate the traversal process using an example graph.
3 Marks
(b)
Find one possible topological ordering for the directed graph with edges: (5→2),(5→0), (4→0), (4→1), (2→3), (3→1).4 Marks
(c)
Given items with weights (w) and profits (p): Item 1: (w=10, p=60), Item 2: (w=20, p=100), Item 3: (w=30, p=120), Capacity (W)=50. Solve using the Greedy method based on profit/weight ratio.
7 Marks
Question 5
(a)
Discuss the Eight Queens Problem in detail. Write the backtracking algorithm and demonstrate the solution process.
3 Marks
(b)
For the Rabin-Karp algorithm, given T = '31415926535', P = '26', base d = 10, and prime q = 13: Compute hash values of pattern and first few text substrings. Identify matching positions.
4 Marks
(c)
Describe the Travelling Salesman Problem (TSP). Why is it considered NP-hard? Discuss any one approximation algorithm for TSP.
7 Marks
OR OPTION
(a)
Explain the Travelling Salesman Problem (TSP) using the Branch and Bound approach with a suitable example.
3 Marks
(b)
Given text T = 'AABAACAADAABAABA' and pattern P = 'AABA', trace the Knuth- Morris-Pratt algorithm execution step-by-step. Show all comparisons and matched positions.
4 Marks
(c)
Explain the class P SPACE and how it differs from P and NP. Provide suitable examples of P SPACE problems.
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 2026, 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.