GTU 3150703 Analysis and Design of Algorithms (ADA) Summer 2025 Question Paper & PDF

Find Big-oh (O) notation of following functions f(n)=3n⁶ + 2 n * lg n + 6n, h(n)= 3n²+ 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)

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).

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

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.