Algorithm Analysis 1. What are the 2 hallmarks of Dynamic Programming? 2. What i

Question

Algorithm Analysis

1. What are the 2 hallmarks of Dynamic Programming?

2. What is memoization? How is it used in Dynamic Programming?

3. Is Divide & Conquer better than Dynamic Programming when there are no overlapping subproblems? Provide an explanation.

4. Write a brute force or recursive method to determine the length of a LCS for the 2 strings: X: 1, 0, 0, 1, 0, 1, 0, 1 and Y: 0, 1, 0, 1, 1, 0, 1, 1, 0

5. Write a Dynamic Programming algorithm to determine the length of a LCS for the 2 strings in 4.

6. Extend the program in (5) to construct a LCS string

Explanation / Answer

Can help you with this:

1)
The two hallmarks of dynamic programming are:
1.Optimal substructure: an optimal solution to a problem contains optimal solutions to subproblems.
2.Overlapping subproblems: a recursive solution contains a "small" number of distinct subproblems repeated many times

2)
Memoization:
>Memoization means recording the results of earlier calculations so that we don’t have to repeat the calculations later. If our code depends on the results of earlier calculations, and if the same calculations are performed over-and-over again, then it makes sense to store interim results (jot results down on a ‘memo’ = memoization) so that we can avoid repeating the math.

How is it used in Dynamic Programming?
>Dynamic Programming is often called Memoization
>Memoization is the top-down technique(start solving the given problem by breaking it down) and dynamic programming is a bottom-up technique(start solving from the trivial sub-problem, up towards the given problem)
>DynamicProgramming finds the solution by starting from the base case(s) and works its way upwards. DP solves all the sub-problems, because it does it bottom-up
>Memoization is DynamicProgramming with the risk of stack overflow is the recursion is deep. DynamicProgramming bottom up does not have this risk.
>In a sense that a problem solvable by memoization will be solvable by DynamicProgramming, but a problem solvable by DynamicProgramming might not be solvable by memoization

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.