3. Common Subwords and Subsequences

Try these first

1. 1.

   Define a subword.

   Hint

   Consider parts of a given word.

2. 2.

   What is the significance of a common subword?

   Hint

   Think of how words relate in meaning or structure.

3. 3.

   What is the longest common subword for 'intersection' and 'section'?

   • inter
   • sect
   • section

   Hint

   Look for contiguous segments in both words.

4. 4.

   True or False: The brute-force method is efficient for very large strings.

   • True
   • False

   Hint

   Consider time complexity.

5. 5.

   Given the strings 'algorithm' and 'logarithm', determine the longest common subword using both brute-force and dynamic programming approaches. Discuss the results and efficiency.

   Hint

   Start by breaking down each method step by step.

6. 6.

   Design a dynamic programming table for the words 'home' and 'some'. Show the filled table and explain how you derived the length of the longest common subword.

   Hint

   Refer to how characters are compared for filling values.