4.6. Tracing Back the LCS

Try these first

1. 1.

   Define the term 'Longest Common Subsequence'.

   Hint

   Think of how sequences can be similar.

2. 2.

   What does dynamic programming involve?

   Hint

   Consider how you tackle complex homework assignments.

3. 3.

   What does the Longest Common Subsequence (LCS) allow?

   • Exact character matching
   • Dropping characters to find sequences
   • Only contiguous sequences

   Hint

   Think about flexibility in matching.

4. 4.

   True or False: Dynamic programming relies on solving problems from the top down.

   • True
   • False

   Hint

   How do you usually approach breaking down tasks?

5. 5.

   Given two sequences X: 'AGGTAB' and Y: 'GXTXAYB', find the longest common subsequence.

   Hint

   Construct an LCS matrix to visualize character matches.

6. 6.

   Analyze how the LCS would differ if both sequences contained repeated characters, such as X: 'AAB', Y: 'ABA'.

   Hint

   Think about how the order of selection affects your results.