Assignment 1: Greedy and Dynamic Programming

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

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

• True

• False

Dynamic programming differs from the greedy method since the greedy method produces only one feasible solution, which may or may not be optimal, while dynamic programming produces all possible sub-problems at most once, one of which guaranteed to be optimal.

• True

• False

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

• Saving value property

• Storing value property

• Memorization

• Mapping

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

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

Consider the two matrices P and Q which are 10 x 20 and 20 x 30 matrices respectively. What is the number of multiplications required to multiply the two matrices?

• 10*20

• 20*30

• 10*30

• 10*20*30