Define the following terms: algorithm, set, function, relation, vector, matrix, linear inequality.
Apply asymptotic notations to sequential search and binary search techniques and find their time complexities in best case, average case and worst case.
Solve the following recurrence relations.
Solve sorting problem using divide and conquer strategy and show its working applying steps on the array [27, 45, 90, 12, 5, 60].
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 |
Explain how assembly line scheduling problem can be solved using dynamic programming method.
Solve the following instance of making change problem using dynamic programming method. N=Rs. 8, Coins: Rs. 1, Rs. 4, Rs.
Solve the following instance of making change problem using greedy method. N=Rs. 8, Coins: Rs. 1, Rs. 4, Rs.
Apply and illustrate how 8-Queen problem can be solved using backtracking method.
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.
Define NP-Complete problem. Define class P and class NP. List the problems that fall under classes P, NP and NPC.
Circulate this solved paper with KaTeX formulas and 1-click AI step solvers to your batchmates on WhatsApp or Telegram.
Official Gujarat Technological University (GTU) examination paper and step-by-step solutions 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.