Counting Boolean Parenthesizations Questions and Answers

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Counting Boolean Parenthesizations”.

1. You are given a boolean expression which consists of operators &, | and ∧ (AND, OR and XOR) and symbols T or F (true or false). You have to find the number of ways in which the symbols can be parenthesized so that the expression evaluates to true. This is the boolean parenthesization problem. Which of the following methods can be used to solve the problem?
a) Dynamic programming
b) Recursion
c) Brute force
d) Dynamic programming, Recursion and Brute force
View Answer

Answer: d
Explanation: Dynamic programming, Recursion and Brute force can be used to solve the Boolean parenthesization problem.

2. Consider the expression T & F | T. What is the number of ways in which the expression can be parenthesized so that the output is T (true)?
a) 0
b) 1
c) 2
d) 3
View Answer

Answer: c
Explanation: The expression can be parenthesized as T & (F | T) and (T & F) | T so that the output is T.

3. Consider the expression T & F ∧ T. What is the number of ways in which the expression can be parenthesized so that the output is T (true)?
a) 0
b) 1
c) 2
d) 3
View Answer

Answer: c
Explanation: The expression can be parenthesized as (T & F) ∧ T or T & (F ∧ T), so that the output is T.

4. Consider the expression T | F ∧ T. In how many ways can the expression be parenthesized so that the output is F (false)?
a) 0
b) 1
c) 2
d) 3
View Answer

Answer: b
Explanation: The expression can be parenthesized as (T | F) ∧ T, so that the output is F (false).

5. Which of the following gives the total number of ways of parenthesizing an expression with n + 1 terms?
a) n factorial
b) n square
c) n cube
d) nth catalan number
View Answer

Answer: d
Explanation: The nth Catalan number gives the total number of ways of parenthesizing an expression with n + 1 terms.

Note: Join free Sanfoundry classes at Telegram or Youtube

6. What is the maximum number of ways in which a boolean expression with n + 1 terms can be parenthesized, such that the output is true?
a) nth catalan number
b) n factorial
c) n cube
d) n square
View Answer

Answer: a
Explanation: The number of ways will be maximum when all the possible parenthesizations result in a true value. The number of possible parenthesizations is given by the nth catalan number.

7. Consider the following dynamic programming implementation of the boolean parenthesization problem:

int count_bool_parenthesization(char *sym, char *op)
{
      int str_len = strlen(sym);
      int True[str_len][str_len],False[str_len][str_len];
      int row,col,length,l;
      for(row = 0, col = 0; row < str_len; row++,col++)
      {
          if(sym[row] == 'T')
          {
              True[row][col] = 1;
              False[row][col] = 0;
          }
          else
          {
              True[row][col] = 0;
              False[row][col] = 1;
          }
      }
      for(length = 1; length < str_len; length++)
      {
          for(row = 0, col = length; col < str_len; col++, row++)
          {
              True[row][col] = 0;
              False[row][col] = 0;
              for(l = 0; l < length; l++)
              {
                  int pos = row + l;
                  int t_row_pos = True[row][pos] + False[row][pos];
                  int t_pos_col = True[pos+1][col] + False[pos+1][col];
                  if(op[pos] == '|')
                  {
                      _______________;
                  }
                  if(op[pos] == '&')
                  {
                      _______________;
                  }
                  if(op[pos] == '^')
                  {
                      _______________;
                  }
              }
          }
      }
      return True[0][str_len-1];
}

Which of the following lines should be added to complete the “if(op[pos] == ‘|’)” part of the code?
a) False[row][col] += True[row][pos] * False[pos+1][col];
True[row][col] += t_row_pos * t_pos_col + False[row][pos] * False[pos+1][col];
b) False[row][col] += False[row][pos] * True[pos+1][col];
True[row][col] += t_row_pos * t_pos_col – True[row][pos] * True[pos+1][col];
c) False[row][col] += True[row][pos] * True[pos+1][col];
True[row][col] += t_row_pos * t_pos_col + True[row][pos] * True[pos+1][col];
d) False[row][col] += False[row][pos] * False[pos+1][col];
True[row][col] += t_row_pos * t_pos_col – False[row][pos] * False[pos+1][col];
View Answer

Answer: d
Explanation: The following lines should be added:
False[row][col] += False[row][pos] * False[pos+1][col];
True[row][col] += t_row_pos * t_pos_col + False[row][pos] * False[pos+1][col];

8. Which of the following lines should be added to complete the “if(op[k] == ‘&’)” part of the following code?

int count_bool_parenthesization(char *sym, char *op)
{
      int str_len = strlen(sym);
      int True[str_len][str_len],False[str_len][str_len];
      int row,col,length,l;
      for(row = 0, col = 0; row < str_len; row++,col++)
      {
          if(sym[row] == 'T')
          {
              True[row][col] = 1;
              False[row][col] = 0;
          }
          else
          {
              True[row][col] = 0;
              False[row][col] = 1;
          }
      }
      for(length = 1; length < str_len; length++)
      {
          for(row = 0, col = length; col < str_len; col++, row++)
          {
              True[row][col] = 0;
              False[row][col] = 0;
              for(l = 0; l < length; l++)
              {
                  int pos = row + l;
                  int t_row_pos = True[row][pos] + False[row][pos];
                  int t_pos_col = True[pos+1][col] + False[pos+1][col];
                  if(op[pos] == '|')
                  {
                      _______________;
                  }
                  if(op[pos] == '&')
                  {
                      _______________;
                  }
                  if(op[pos] == '^')
                  {
                      _______________;
                  }
              }
          }
      }
      return True[0][str_len-1];
}

a) True[row][col] += False[row][pos] * False[pos+1][col];
False[row][col] += t_row_pos * t_pos_col – True[row][pos] * True[pos+1][col];
b) True[row][col] += True[row][pos] * True[pos+1][col];
False[row][col] += t_row_pos * t_pos_col – True[row][pos] * True[pos+1][col];
c) True[row][col] += True[row][pos] * False[pos+1][col];
False[row][col] += t_row_pos * t_pos_col – False[row][pos] * True[pos+1][col];
d) True[row][col] += False[row][pos] * True[pos+1][col];
False[row][col] += t_row_pos * t_pos_col – False[row][pos] * True[pos+1][col];
View Answer

Answer: b
Explanation: The following lines should be added:
True[row][col] += True[row][pos] * True[pos+1][col];
False[row][col] += t_row_pos * t_pos_col – True[row][pos] * True[pos+1][col];

9. What is the time complexity of the following dynamic programming implementation of the boolean parenthesization problem?

int count_bool_parenthesization(char *sym, char *op)
{
      int str_len = strlen(sym);
      int True[str_len][str_len],False[str_len][str_len];
      int row,col,length,l;
      for(row = 0, col = 0; row < str_len; row++,col++)
      {
          if(sym[row] == 'T')
          {
              True[row][col] = 1;
              False[row][col] = 0;
          }
          else
          {
              True[row][col] = 0;
              False[row][col] = 1;
          }
      }
      for(length = 1; length < str_len; length++)
      {
          for(row = 0, col = length; col < str_len; col++, row++)
          {
              True[row][col] = 0;
              False[row][col] = 0;
              for(l = 0; l < length; l++)
              {
                  int pos = row + l;
                  int t_row_pos = True[row][pos] + False[row][pos];
                  int t_pos_col = True[pos+1][col] + False[pos+1][col];
                  if(op[pos] == '|')
                  {
                      False[row][col] += False[row][pos] * False[pos+1][col];
                      True[row][col] += t_row_pos * t_pos_col - False[row][pos] * False[pos+1][col];;
                  }
                  if(op[pos] == '&')
                  {
                     True[row][col] += True[row][pos] * True[pos+1][col];
                     False[row][col] += t_row_pos * t_pos_col - True[row][pos] * True[pos+1][col];
                  }
                  if(op[pos] == '^')
                  {
                     True[row][col] += True[row][pos] * False[pos+1][col] 
                                      + False[row][pos] * True[pos + 1][col];
                     False[row][col] += True[row][pos] * True[pos+1][col] 
                                       + False[row][pos] * False[pos+1][col];
                  }
              }
          }
      }
      return True[0][str_len-1];
}

a) O(1)
b) O(n)
c) O(n²)
d) O(n³)
View Answer

Answer: d
Explanation: The time complexity of the above dynamic programming implementation is O(n³).

10. What is the space complexity of the following dynamic programming implementation of the boolean parenthesization problem?

int count_bool_parenthesization(char *sym, char *op)
{
      int str_len = strlen(sym);
      int True[str_len][str_len],False[str_len][str_len];
      int row,col,length,l;
      for(row = 0, col = 0; row < str_len; row++,col++)
      {
          if(sym[row] == 'T')
          {
              True[row][col] = 1;
              False[row][col] = 0;
          }
          else
          {
              True[row][col] = 0;
              False[row][col] = 1;
          }
      }
      for(length = 1; length < str_len; length++)
      {
          for(row = 0, col = length; col < str_len; col++, row++)
          {
              True[row][col] = 0;
              False[row][col] = 0;
              for(l = 0; l < length; l++)
              {
                  int pos = row + l;
                  int t_row_pos = True[row][pos] + False[row][pos];
                  int t_pos_col = True[pos+1][col] + False[pos+1][col];
                  if(op[pos] == '|')
                  {
                      False[row][col] += False[row][pos] * False[pos+1][col];
                      True[row][col] += t_row_pos * t_pos_col - False[row][pos] * False[pos+1][col];;
                  }
                  if(op[pos] == '&')
                  {
                     True[row][col] += True[row][pos] * True[pos+1][col];
                     False[row][col] += t_row_pos * t_pos_col - True[row][pos] * True[pos+1][col];
                  }
                  if(op[pos] == '^')
                  {
                     True[row][col] += True[row][pos] * False[pos+1][col] 
                                       + False[row][pos] * True[pos + 1][col];
                     False[row][col] += True[row][pos] * True[pos+1][col] 
                                       + False[row][pos] * False[pos+1][col];
                  }
              }
          }
      }
      return True[0][str_len-1];
}

a) O(1)
b) O(n)
c) O(n²)
d) O(n³)
View Answer

Answer: c
Explanation: The space complexity of the above dynamic programming implementation is O(n²).

11. What is the output of the following code?

#include<stdio.h>
#include<string.h>
int count_bool_parenthesization(char *sym, char *op)
{
     int str_len = strlen(sym);
     int True[str_len][str_len],False[str_len][str_len];
     int row,col,length,l;
     for(row = 0, col = 0; row < str_len; row++,col++)
     {
         if(sym[row] == 'T')
         {
             True[row][col] = 1;
             False[row][col] = 0;
         }
         else
         {
             True[row][col] = 0;
             False[row][col] = 1;
         }
     }
     for(length = 1; length < str_len; length++)
     {
         for(row = 0, col = length; col < str_len; col++, row++)
         {
             True[row][col] = 0;
             False[row][col] = 0;
             for(l = 0; l < length; l++)
             {
                 int pos = row + l;
                 int t_row_pos = True[row][pos] + False[row][pos];
                 int t_pos_col = True[pos+1][col] + False[pos+1][col];
                 if(op[pos] == '|')
                 {
                     False[row][col] += False[row][pos] * False[pos+1][col];
                     True[row][col] += t_row_pos * t_pos_col - False[row][pos] * False[pos+1][col];
                 }
                 if(op[pos] == '&')
                 {
                     True[row][col] += True[row][pos] * True[pos+1][col];
                     False[row][col] += t_row_pos * t_pos_col - True[row][pos] * True[pos+1][col];
                 }
                 if(op[pos] == '^')
                 {
                     True[row][col] += True[row][pos] * False[pos+1][col] 
                                       + False[row][pos] * True[pos + 1][col];
                     False[row][col] += True[row][pos] * True[pos+1][col] 
                                       + False[row][pos] * False[pos+1][col];
                 }
             }
         }
     }
     return True[0][str_len-1];
}
int main()
{
     char sym[] = "TTTT";
     char op[] = "|^^";
     int ans = count_bool_parenthesization(sym,op);
     printf("%d",ans);
     return 0;
}