Counting Boolean Parenthesizations in Data Structure And Algorithm: Practice MCQ Questions and Answers

7 practice sets · Page 1 of 1

Data Structure And AlgorithmMediumDynamic ProgrammingCounting Boolean Parenthesizations

Which of the following lines should be added to complete the "if(op[pos] == '|')" part of the code?

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];

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];

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];

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 and explanation

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

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];

Data Structure And AlgorithmMediumDynamic ProgrammingCounting Boolean Parenthesizations

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?

nth catalan number

n factorial

n cube

n square

Answer and explanation

Correct Answer: A — nth catalan number

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.

Data Structure And AlgorithmMediumDynamic ProgrammingCounting Boolean Parenthesizations

Which of the following gives the total number of ways of parenthesizing an expression with n + 1 terms?

n factorial

n square

n cube

nth catalan number

Answer and explanation

Correct Answer: D — nth catalan number

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

Data Structure And AlgorithmMediumDynamic ProgrammingCounting Boolean Parenthesizations

Consider the expression T | F ∧ T. In how many ways can the expression be parenthesized so that the output is F (false)?

Answer and explanation

Correct Answer: B — 1

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

Data Structure And AlgorithmMediumDynamic ProgrammingCounting Boolean Parenthesizations

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)?

Answer and explanation

Correct Answer: C — 2

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

Data Structure And AlgorithmMediumDynamic ProgrammingCounting Boolean Parenthesizations

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)?

Answer and explanation

Correct Answer: C — 2

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

Data Structure And AlgorithmMediumDynamic ProgrammingCounting Boolean Parenthesizations

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?

Dynamic programming

Recursion

Brute force

Dynamic programming, Recursion and Brute force

Answer and explanation

Correct Answer: D — Dynamic programming, Recursion and Brute force

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

Printing this content is disabled

Counting Boolean Parenthesizations in Data Structure And Algorithm: Practice MCQ Questions and Answers