Find Big-oh (O) notation of following functions f(n)=3n6 + 2 n * lg n + 6n, h(n)= 3n2+ 6n*lgn+ 2n2.5
Write binary search algorithm and analyze it for worst case time complexity. Represent its time complexity using Big-oh (O) notation.
If P(n) = a0+ a1 n + a2 n2 + . . . . . . + amnm then prove that P(n) = Ω(nm). Here a0, a1, a2 …..am are constants and am>0.
Solve following recurrence relation using suitable method and express your answer using Big-oh (O) notation. T(n) = T(n/6) + T(5n/6) + Ө(n)
Solve following recurrence relations using suitable method and express your answer using Big-oh (O) notation.
Arrange the following growth rates from the lowest to highest asymptotic order: O(n log n), O(n2n), Ω(log n), O(n0.5), O(n!), Ω(2n), O(n0.5 log n)
Write the recurrence relation for the quick sort on input instance: 15, 19, 20, 25, 32, 37, 50, 62, 70. Comment on the nature of input i.e. best case, average case or worst case.
Write greedy algorithm for activity selection problem. Give its time complexity. For following intervals, select the activities according to your algorithm. I1 (1-3), I2 (0-2), I3 (3-6), I4 (2-5), I5 (5-8), I6 (3-10), I7 (7-9).
Write any algorithm (need not to have meaningful) which has a time complexity of O(1) and also includes a loop statement. Also, confirm its time complexity of O(1) using tabular method.
Also, write time complexity of DFS algorithm. C G A B F H D E
What is Principle of Optimality in dynamic programming? Explain it with example.
What is knapsack problem? Using greedy algorithm find an optimal solution for fractional knapsack instance n=7, M =17, profits p[ ] = {10,5,15,7,6,16,4} and weights w[ ] = {2,3,5,7,1,4,1}.
Find the optimal way of multiplying following matrices using dynamic programming. Also indicate optimal number of multiplications required. A:2 x 3, B: 3 x 5, C:5 x 6, D: 6 x 2, E: 2 x
What is the Travelling Salesman Problem (TSP)? Why TSP is considered an NP-hard problem?
Illustrate the working of Kruskal’s algorithm using greedy technique. Take the suitable graph for illustration.
Find the longest common subsequence for the following two sequences using dynamic programming. Show the complete process and indicate the time complexity. X = 10101010011 Y = 101001
Explain the backtracking strategy to solve optimization problem. Explain how it can be applied to find the solution for 4-queen problem.
Given a text and a pattern, write the naive string matching algorithm to find all occurrences of the pattern in the text. Use the text "ABCABCABC" and the pattern "ABC". Also, give time complexity of naive string matching algorithm.
What is a polynomial reduction? Explain its role in proving NP- completeness.
Give example of any NP complete problem. Explain how to prove that particular problem is NP complete.
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 (ADA) (Summer 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.