Quiz 3 - Dynamic Programming

Question 1

What are the major required aspects in a problem in order to apply Dynamic Programming Technique?

• Whether a problem can be divided or not
• Be able to solve using top down and bottom up approach
• Optimal Substructure and Overlapping subproblems
• Base case to stop recurrence

Answer 1

• Optimal Substructure and Overlapping subproblems

Question 2

In which of the following approaches we start with the base case and proceed to solve the bigger subproblems?

Answer 2

Bottom-Up Approach

Question 3

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

Answer 3

Memoization

Question 4

The difference between Divide and Conquer Approach and Dynamic Programming is?

• Use of recurrence formula
• The base case
• The way we divide the sub-problems
• Whether the sub-problems overlap or not

Answer 4

• Whether the sub-problems overlap or not

Question 5

A binary search algorithm searches for a target value within a sorted array. Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until the target value is found or until a search can no longer be performed. This problem can be solved using which of the techniques?

• Dynamic Programming
• None of the options
• Any of the two techniques
• Divide and Conquer

Answer 5

• Divide and Conquer

there are repeatable subproblems, but not Dynamic Programming because there are no overlapping sub-problems.

Question 6

In the Longest Common Subsequence problem assume we are comparing two strings of lengths m and n. In the bottom-up approach the solution we build a 2-Dimensional array called Cache[m][n]. The final solution was obtained by accessing which element of the cache?

give the location of the element in the 2d array.

Answer 6

The element in the bottom right corner of the cache[m][n]

Question 7

In
[ Select ]
we start with the base case and build the solution starting from base case. In
[ Select ]
we start solving the the bigger problem proceed towards the base case.

Answer 7

bottom-up

top-down