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