Counting Boolean Parenthesizations in Data Structure And Algorithm : Practice MCQ Questions & Answers with Explanations

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

View Answer

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

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

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

View Answer

Correct Answer: A — nth catalan number

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.

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

View Answer

Correct Answer: D — nth catalan number

Explanation:

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

View Answer

Correct Answer: B — 1

Explanation:

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

View Answer

Correct Answer: C — 2

Explanation:

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

View Answer

Correct Answer: C — 2

Explanation:

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

View Answer

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

Explanation:

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