4.. Longest Common Subsequence

Try these first

1. 1.

   Define the term 'Longest Common Subsequence'.

   Hint

   Think about how characters can match in order.

2. 2.

   What is dynamic programming?

   Hint

   Recall how certain algorithms optimize problem-solving.

3. 3.

   What does LCS stand for?

   • Longest Common Subsegment
   • Longest Common Subsequence
   • Least Common Subsequence

   Hint

   Consider what 'subsequence' implies in mathematics.

4. 4.

   True or False: LCS allows rearranging characters to find matches.

   • True
   • False

   Hint

   Focus on the definition of subsequences.

5. 5.

   Given the sequences 'ABCDGH' and 'AEDFHR', compute the LCS and explain the significance of your stepwise approach.

   Hint

   Keep track of matches and visualize them in a grid.

6. 6.

   Consider the sequences 'XYZ' and 'YZX'. Assess the LCS and discuss the approach for characters that don't match.

   Hint

   Plot out comparisons in a side-by-side fashion for clarity.