UnFoldPrep
Browse Archive
Gujarat Technological UniversitySummer 2023 Examination

GTU 3150703 Analysis and Design of Algorithms (ADA) Summer 2023 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 Hours2:30 PM – 5:00 PM
Paper Structure5 QuestionsWith internal OR choices
Jump toQ1Q2Q3Q4Q5

Question 1

14 MarksMedium
(a)
Define following terms:
i)Big O Notation,
ii)Big Theta Notation,
iii)Big Omega Notation.
3 Marks
(b)

Perform Bucket sort for following sequence: 30, 12, 22, 66, 48, 27, 35, 43, 47, 41.

4 Marks
(c)

Explain the bubble sort algorithm and derive its best case, worst case, and average case time complexity.

7 Marks

Question 2

14 MarksMedium
(a)
Define Algorithms and characteristics of algorithms.
3 Marks
(b)

What is a recurrence? Solve recurrence equation for T (n) =T (n-1) + 1 using substitution method.

4 Marks
(c)

Discuss Binary search algorithm, also write and solve its recurrence relation.

7 Marks
OR OPTION
(c)
Explain Merge Sort algorithm with suitable example.
7 Marks

Question 3

14 MarksMedium
(a)
Explain principle of optimality with suitable example.
3 Marks
(b)
Explain advantages and disadvantages of dynamic programming.
4 Marks
(c)

Given the denominations: d1=1, d2=4, d3=6. Calculate for making change of Rs. 8 using dynamic programming.

7 Marks
OR OPTION
(a)
Explain Weighted Graph, Undirected Graph, Directed Graph.
3 Marks
(b)
Discuss advantages and disadvantages of greedy algorithm.
4 Marks
(c)

Consider weights w=(3,4,6,5) and profit v=(2,3,1,4) and Knapsack capacity W=8. Find the maximum profit using dynamic approach.

7 Marks

Question 4

14 MarksMedium
(a)
Find an optimal Huffman code for the following set of frequency. a :

40, b: 20, c: 15, d: 30, e: 10.

3 Marks
(b)
Explain depth first traversal using suitable example.
4 Marks
(c)

Draw the minimum spanning tree correspond to following graph using Prim’s algorithm and find the MST weight:

7 Marks
OR OPTION
(a)

Differentiate between Kruskal’s algorithm and Prim’s algorithm for finding MST.

3 Marks
(b)
Explain the need of topological Sort with example.
4 Marks
(c)

Draw the minimum spanning tree correspond to following graph using Kruskal’s algorithm and find weight of MST:

7 Marks

Question 5

14 MarksMedium
(a)
Explain Spurious hits with an example.
3 Marks
(b)
Write the pseudocode for Naïve String-Matching Algorithm.
4 Marks
(c)

What is state space tree. How do you solve the Eight queens problem using backtracking with the help of state space tree.

7 Marks
OR OPTION
(a)
Explain polynomial time reduction.
3 Marks
(b)

Differentiate between Backtracking and Branch-and-Bound algorithms.

4 Marks
(c)

Define P, NP, NP complete and NP-Hard problems. Give examples of each.

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) (Summer 2023, 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