16.2.4. Initial Conditions for Bad Strings

Try these first

1. 1.

   What is a bad string?

   Hint

   Think of substrings that should not appear.

2. 2.

   Define a recurrence relation.

   Hint

   Focus on how a sequence can be defined recursively.

3. 3.

   What qualifies as a bad string?

   • A string with a recurring pattern
   • A string without a specified substring
   • A string of any length

   Hint

   Focus on the definition of bad strings presented in class.

4. 4.

   True or False: Recurrence relations can only define numeric sequences.

   • True
   • False

   Hint

   Think about how we've defined strings using recurrence.

5. 5.

   Calculate the total number of valid bit strings of length 5 that do not contain '000'.

   Hint

   Set your base cases right from 0 to 4.

6. 6.

   Propose an algorithm that can compute the number of valid strings based on the discussed recurrence relations efficiently.

   Hint

   Think about how to minimize recalculations by storing previous results.