VCE-FN-09.05.2024

Which of the following is/are property/properties of a dynamic programming problem?

• Optimal substructure
• Overlapping subproblems
• Greedy approach
• Both optimal substructure and overlapping subproblems

If an optimal solution can be created for a problem by constructing optimal solutions for its subproblems, the problem possesses ____________ property.

• Overlapping subproblems
• Optimal substructure
• Memoization
• Greedy

If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called _____________

• Dynamic programming
• Greedy
• Divide and conquer
• Recursion

In dynamic programming, the technique of storing the previously calculated values is called ___________

• Saving value property
• Storing value property
• Memoization
• Mapping

When a top-down approach of dynamic programming is applied to a problem, it usually _____________

• Decreases both, the time complexity and the space complexity
• Decreases the time complexity and increases the space complexity
• Increases the time complexity and decreases the space complexity
• Increases both, the time complexity and the space complexity

Which of the following problems is NOT solved using dynamic programming?

• 0/1 knapsack problem
• Matrix chain multiplication problem
• Edit distance problem
• Fractional knapsack problem

Which of the following problems should be solved using dynamic programming?

• Mergesort
• Binary search
• Longest common subsequence
• Quicksort

Which of the following is not a characteristic of dynamic programming?

• Overlapping subproblems
• Optimal substructure
• Recursion
• Divide and Conquer

Which of the following is an example of a problem that can be solved using memoization in dynamic programming?

• Computing the nth prime number
• Finding the minimum cost path in a weighted graph
• Sorting a list of string in lexicographic order
• Computing the edit distance two strings

What is dynamic programming in data structures?

• A technique for designing efficient algorithms by breacking down a problem into smaller subproblems
• A way to store and organize data in a computer program
• A process of optimizing memory usage in a program
• Amethod for creating algorithms that use only constant space