4.1. General Problem

Try these first

1. 1.

   Define the longest common subsequence (LCS).

   Hint

   Break down the definition into parts: 'longest', 'subsequence', and 'order'.

2. 2.

   What does dynamic programming help with in problem-solving?

   Hint

   Think of a way to avoid calculating the same thing multiple times.

3. 3.

   What strategy does LCS utilize to find similarities between sequences?

   • Exact matching
   • Dropping letters
   • Random selection

   Hint

   Consider the goal of finding the longest match, not just short ones.

4. 4.

   True or False: LCS can only be applied to genetic sequences.

   • True
   • False

   Hint

   Think broadly about how LCS might be useful in texts or sentences.

5. 5.

   Given the sequences 'AGGTAB' and 'GXTXAYB', compute the LCS and explain how to arrive at your answer.

   Hint

   Visualize a grid; track matching characters and build on previous results.

6. 6.

   Critique the efficiency of LCS utilizing brute force versus dynamic programming.

   Hint

   Understand the relation between the size of input and the number of calculations involved.