Dynamic Programming DAA

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

• Saving value property

• Storing value property

• Memorization

• Mapping

Consider the two strings “”(empty string) and “abcd”. What is the edit distance between the two strings?

• 0

• 3

• 4

• None of the above

What are 2 things required in order to successfully use the dynamic programming technique?

• Optimal sub structure and overlapping sub problems

• A problem that can’t be sub divided and is complex

• Non overlapping sub problems and intervals

• Recursion and a problem that is complex

Dynamic Programming is often used for (choose all that apply):

• Optimization problems that involve making a choice that leave one or more subproblems to be solved.

• Problems previously solved using divide and conquer that have over lapping subproblems

• Non polynomial solution problems

• Subproblems where resources are shared

The difference between Divide and Conquer and Dynamic Programming is:

• The division of problems and combination of subproblems

• Whether the sub problems overlap or not

• The way we solve the base case

• The depth of recurrence

If a problem can be broken into subproblems which are reused several times, the problem possesses ____________ property.

• Overlapping subproblems

• Optimal substructure

• Memorization

• Greedy

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

Find the longest increasing subsequence for the given sequence:

{10, -10, 12, 9, 10, 15, 13, 14}

• {10, 12, 15}

• {10, 12, 13, 14}

• {-10, 12, 13, 14}

• {-10, 9, 10, 13, 14}

For any given sequence, there will ALWAYS be a unique increasing subsequence with the longest length.

• True

• False

You are given a knapsack that can carry a maximum weight of 60. There are 4 items with weights {20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of the items you can carry using the knapsack?

• 170

• 200

• 160

• 90