UnFoldPrep
Browse Archive
Gujarat Technological UniversityWinter 2025 Examination

GTU 3150703 Analysis and Design of Algorithms (ADA) Winter 2025 Paper Solution & PDF

B.E. · Computer Engineering · Semester 5 · Subject Code: 3150703
Download Official GTU PDF
Share:
Total Marks70 MarksExternal theory exam
Passing Marks23 Marks33% minimum cutoff
Exam Duration2.5 Hours10:30 AM – 1:00 PM
Paper Structure5 QuestionsWith internal OR choices
Jump toQ1Q2Q3Q4Q5

Question 1

14 MarksMedium
(a)
State the time complexity of following problems in descending order:

Matrix multiplication, inserting element in binary search tree, inert node at beaning in linked list, linear search, selection sort, merge sort.

3 Marks
(b)
Summarize and explain the properties of algorithm
4 Marks
(c)
Apply bubble sort on the given data sequence: 77, 22, 55, 11, 33, 66, 44
7 Marks

Question 2

14 MarksMedium
(a)
Write the algorithm for binary search
3 Marks
(b)
Identify the constant c, n0 and upper bound for given recurrences:

T(n) = 4n2 + 3n – 4 T(n) = 6n3 – 8n2 + 9n +

4 Marks
(c)
Illustrate and solve recurrence for best and worst case of quick sort
7 Marks
OR OPTION
(c)

Construct solution using Merge sort on the given data sequence: 88, 77, 22, 55, 11, 33, 66, 99, 44. Also state its recurrence and solve it.

7 Marks

Question 3

14 MarksMedium
(a)
Define principle of Optimality. Discuss with example.
3 Marks
(b)
Differentiate: Dynamic programming vs divide and conquer
4 Marks
(c)

Solve following instance of knapsack problem using dynamic programming: W = [1, 2, 5, 6, 10], V = [1, 6, 18, 22, 30] and Knapsack capacity M =

7 Marks
OR OPTION
(a)
Define the characteristics of greedy algorithms
3 Marks
(b)
Explain activity selection problem.
4 Marks
(c)

Infer the Longest Common Subsequence for following strings: X = 10010100 Y = 10011

7 Marks

Question 4

14 MarksMedium
(a)
State and explain methods to represent the graph
3 Marks
(b)
Differentiate: BFS vs DFS
4 Marks
(c)

Outline algorithm for Prim’s method and find MST for given graph using Prim’s method

GTU Analysis and Design of Algorithms (3150703) Winter 2025 Question 4(c) Diagram
7 Marks
OR OPTION
(a)
Define Articulation point, Acyclic Directed Graph, Back Edge
3 Marks
(b)
Find prefix code for given data. A: 45, B: 30, C: 15, D: 12, E:
4 Marks
(c)

Outline algorithm for Kruskal’s method and find MST for the graph given in Figure 1, using Kruskal’s method

GTU Analysis and Design of Algorithms (3150703) Winter 2025 Question 4 OR (c) Diagram
7 Marks

Question 5

14 MarksMedium
(a)
Show naïve string matching algorithm with example.
3 Marks
(b)
Find topological sequence of vertices for the graph given in Figure 1.

Consider A is starting vertex.

GTU Analysis and Design of Algorithms (3150703) Winter 2025 Question 5(b) Diagram
4 Marks
(c)

Explain backtracking method. What is 4 queen problem? Show its all possible solutions.

7 Marks
OR OPTION
(a)
Explain polynomial time reduction
3 Marks
(b)
Compare and contrast: Backtracking vs. Branch and Bound
4 Marks
(c)

What do you mean by spurious hits? For modulo q=13, how many spurious hits does the Rabin-Karp encounters for the text T = 4359023141526739921 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.

Related papers

About this Examination Paper & Attribution

Official Gujarat Technological University (GTU) examination paper and step-by-step solutions for Analysis and Design of Algorithms (ADA) (Winter 2025, 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.

Download PDF