20.4.1. Formulation of Valid Strings

Try these first

1. 1.

   Define a valid string in the context of parentheses.

   Hint

   Think about matching pairs.

2. 2.

   Provide two examples of valid strings.

   Hint

   Focus on balanced pairs.

3. 3.

   What is the definition of a valid parenthesis string?

   • A string that is completely empty
   • A string where each '(' matches a ')'
   • A string with more ')' than '('

   Hint

   Think about what makes a string valid!

4. 4.

   True or False: The formula C(n) = ∑C(k)C(n-k-1) is a recurrence relation for Catalan numbers.

   • True
   • False

   Hint

   Recall the formation of the recurrence.

5. 5.

   Create and describe a new problem related to valid parenthesis without violating the matching condition.

   Hint

   Think about restrictions on placement.

6. 6.

   Propose an algorithm to count valid strings of n parenthesis using dynamic programming.

   Hint

   Look into how states can be represented.