Back to the 2024 paper
Similar questions
Design and Analysis of Algorithms What is the primary advantage of dynamic programming over brute-force algorithms? (i) Dynamic programming guarantees finding the global optimum. (ii) Dynamic programming reduces the time complexity by avoiding redundant computations. (iii) Dynamic programming simplifies the problem by dividing it into smaller subproblems. (iv) Dynamic programming is more intuitive to implement.20232mDesign & Analysis of AlgorithmsCompare the various programming paradigms such as divide-and-conquer, dynamic programming and greedy approach.20197mDesign & Analysis of AlgorithmsDistinguish greedy method and dynamic programming20247mDesign and Analysis of Algorithms Differentiate between divide & conquer, greedy method and dynamic programming with suitable examples.20227m
PreviousWhat is the Master's Theorem? State the general form and the three cases of the theorem. Use it to solve the following recurrence relations: (i) T(n) = 2T(n/2) + n (ii) T(n) = 3T(n/2) + n^2 (iii) T(n) = 2T(n/2) + n/\log n Explain which case applies in each situation.NextThe 0/1 Knapsack Problem is a classical combinatorial optimization problem. Explain how this problem can be solved using: (i) Brute-force method (ii) Greedy method (iii) Dynamic Programming (iv) Branch-and-Bound For each approach, explain the algorithm, time complexity, and limitations. Highlight why the greedy method may not always yield the optimal solution.