4.4. Subproblem Dependency

Try these first

1. 1.

   Define Longest Common Subsequence in your own words.

   Hint

   Think about patterns in sequences.

2. 2.

   What is dynamic programming?

   Hint

   Consider how problems can be simplified.

3. 3.

   What is the time complexity of finding LCS using dynamic programming?

   • O(m*n)
   • O(m+n)
   • O(m^2)

   Hint

   Remember how we build the solution.

4. 4.

   True or False: LCS can include characters that are not adjacent in given sequences.

   • True
   • False

   Hint

   Think about the definition of a subsequence.

5. 5.

   Suppose you have string A: 'ABCBDAB' and string B: 'BDCAB'. Calculate the LCS, and provide the DP table.

   Hint

   Start with filling the first two rows based on matches and mismatches.

6. 6.

   Discuss how LCS can be extended to more than two sequences. What complexities arise?

   Hint

   Consider expanding the dimension of the DP table for more sequences.