3.3. Inductive Observation

Try these first

1. 1.

   Define a subword.

   Hint

   Think about smaller parts of a word.

2. 2.

   What is the brute force algorithm?

   Hint

   It's a straightforward but inefficient way.

3. 3.

   What is the longest common subword of 'internet' and 'intranet'?

   • inter
   • net
   • intra

   Hint

   Look for the longest matching segment.

4. 4.

   True or False: In a brute force approach, we do not try all possible combinations.

   • True
   • False

   Hint

   Consider how brute force methods work.

5. 5.

   Given the strings 'ABCDEF' and 'ABXYEF', find the longest common subword and its length.

   Hint

   Identify segments that appear in both strings.

6. 6.

   In an algorithm using dynamic programming, explain how you would track the maximum common subword length during runtime.

   Hint

   Consider how the table fills with common segment data.