NEW
Font size
WorksheetsDynamic Programming_CSE
Total questions: 10
Worksheet time: 5mins
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.
