- Computer Science Engineering (CSE)
- Design and Analysis of Algorithms
- When a top-down approach of dynamic prog...

Q. |
## When a top-down approach of dynamic programming is applied to a problem, it usually |

A. | decreases both, the time complexity and the space complexity |

B. | decreases the time complexity and increases the space complexity |

C. | increases the time complexity and decreases the space complexity |

D. | increases both, the time complexity and the space complexity |

Answer» B. decreases the time complexity and increases the space complexity | |

Explanation: 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. |

View all MCQs in:
Design and Analysis of Algorithms

- When dynamic programming is applied to a problem, it takes far less time as compared to other methods that don’t take advantage of overlapping subproblems.
- You are given infinite coins of N denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the time complexity of a dynamic programming implementation used to solve the coin change problem?
- In the dynamic programming implementation of the assembly line scheduling problem, how many lookup tables are required?
- What is the time complexity of the above dynamic programming implementation of the assembly line scheduling problem?
- The dynamic programming implementation of the maximum sum rectangle problem uses which of the following algorithm?
- In what time can the Hamiltonian path problem can be solved using dynamic programming?
- What is the worst case time complexity of dynamic programming solution of set partition problem(sum=sum of set elements)?
- What will be the auxiliary space complexity of dynamic programming solution of set partition problem(sum=sum of set elements)?
- Recursive solution of subset sum problem is faster than dynamic problem solution in terms of time complexity.
- Recursive solution of Set partition problem is faster than dynamic problem solution in terms of time complexity.

Login to Continue

It will take less than 2 minutes

Report MCQ