Dynamic Programming_CSE

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

• Optimal substructure

• Overlapping subproblems

• Greedy approach

• d) 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 broken into subproblems which are reused several times, 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

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.

• True

• False

A greedy algorithm can be used to solve all the dynamic programming problems.

• True

• False

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

Dynamic programming divides problems into a number of

• conflicting objective functions.

• decision stages.

• unrelated constraints.

• policies.

The relationship between stages of a dynamic programming problem is called a(n)

• state.

• random variable.

• node.

• Transformation.

In dynamic programming, the output to stage n become the input to

• stage n-1.

• stage n itself.

• stage n+1.

• stage n-2.