Q.1
14 Marks(a)
Define the following terms: algorithm, set, function, relation, vector, matrix, linear inequality.
(b)
1State the general characteristics of the greedy method.
2State the general characteristic of the dynamic programming method.
Gujarat Technological UniversitySummer 2024 examination
GTU 2150703 Analysis and Design of Algorithms Summer 2024 Question Paper & PDF
B.E. · Computer Engineering · Semester 5 · Subject code 2150703
- 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.
Q.2
14 Marks(a)
Apply asymptotic notations to sequential search and binary search techniques and find their time complexities in best case, average case and worst case.
(b)
Solve the following recurrence relations.
1T(n) = 2T(n/2) + n
2T(n) = T(n-1) + n
OR
(b)
Prove that Hamiltonian problem is NP-Complete problem.
Q.3
14 Marks(a)
Solve sorting problem using divide and conquer strategy and show its working applying steps on the array [27, 45, 90, 12, 5, 60].
(b)
Solve following knapsack problem using greedy method. Knapsack capacity = 60 kg.
| Item | Weight | Value |
|---|---|---|
| A | 5 | 30 |
| B | 22 | 77 |
| C | 10 | 40 |
| D | 15 | 45 |
OR
(a)
1Illustrate the operation of BUILD-MAX-HEAP on the array A = (5, 3, 17, 10, 84, 19, 6, 22, 9).
2Illustrate the operation of HEAPSORT on the array A = (5, 13, 2, 25, 7, 17, 20, 8, 4).
1)Illustrate the operation of BUILD-MAX-HEAP on the array A = (5, 3, 17, 10,
84, 19, 6, 22,
9).
2. Illustrate the operation of HEAPSORT on the array A = (5, 13, 2, 25, 7, 17,
20, 8,
4).
(b)
Explain how assembly line scheduling problem can be solved using dynamic programming method.
Q.4
14 Marks(a)
Solve the following instance of making change problem using dynamic programming method. N=Rs. 8, Coins: Rs. 1, Rs. 4, Rs.
(b)
Write depth first search algorithm and show its execution on a sample graph.
OR
(a)
Solve the following instance of making change problem using greedy method. N=Rs. 8, Coins: Rs. 1, Rs. 4, Rs.
(b)
Write breadth first search algorithm and show its execution on a sample graph.
Q.5
14 Marks(a)
Apply and illustrate how 8-Queen problem can be solved using backtracking method.
(b)
Write Naïve string matching algorithm. Apply it to the pattern P = 0001 and the text T = 000010001010001. Compute the number of comparisons required to find pattern P in the text T.
OR
(a)
Find all the connected components from the following graph.
(b)
Define NP-Complete problem. Define class P and class NP. List the problems that fall under classes P, NP and NPC.
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 (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.