250+ TOP MCQs on Counting Boolean Parenthesizations and Answers

Data Structure Multiple Choice Questions 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

Answer: d
Clarification: 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

Answer: c
Clarification: 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

Answer: c
Clarification: 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

Answer: b
Clarification: 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

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

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

Answer: a
Clarification: 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];

Answer: d
Clarification: 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];

Answer: b
Clarification: 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(n2)
d) O(n3)
Answer: d
Clarification: The time complexity of the above dynamic programming implementation is O(n3).

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(n2)
d) O(n3)

Answer: c
Clarification: The space complexity of the above dynamic programming implementation is O(n2).

11. What is the output of the following code?

#include
#include
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;
}

a) 1
b) 2
c) 3
d) 4
View Answer

Answer: d
Clarification: The output of the above program is 4.

and Answers.

Leave a Reply

Your email address will not be published. Required fields are marked *