Design and Analysis of Algorithms MCQs | Page - 24

 dynamic programming calculates the value of a subproblem only once, while other methods that don’t take advantage of the overlapping subproblems property may calculate the value of the same subproblem several times. so, dynamic programming saves the time of recalculation and takes far less time as compared to other methods that don’t take advantage of the overlapping subproblems property.

 a greedy algorithm gives optimal solution for all subproblems, but when these locally optimal solutions are combined it may not result into a globally optimal solution. hence, a greedy algorithm cannot be used to solve all the dynamic programming problems.

 memoization is the technique

 the top-down approach uses the memoization technique which stores the previously calculated values. due to this, the time complexity is decreased but the space complexity is increased.

 the fractional knapsack problem is solved using a greedy algorithm.

 the longest common subsequence problem has both, optimal substructure and overlapping subproblems. hence, dynamic programming should be used the solve this problem.

 the recurrence relation is given by fibo(n) = fibo(n – 1) + fibo(n – 2). so, the time complexity is given by:

 the recursive implementation doesn’t store any values and calculates every value from scratch. so, the space complexity is o(1).

 to calculate the nth term, the for loop runs (n – 1) times and each time a for loop is run, it takes a constant time.

 the coin change problem has overlapping subproblems(same subproblems are solved multiple times) and optimal substructure(the solution to the problem can