gs gs122 Dynamic Programming - Counting Boolean Parenthesizations - Quiz No.1
gs gs122 Data Communication and Computer Network Quiz
This quiz belongs to book/course code gs gs122 Data Communication and Computer Network of gs organization. We have 268 quizzes available related to the book/course Data Communication and Computer Network. This quiz has a total of 10 multiple choice questions (MCQs) to prepare and belongs to topic Dynamic Programming. NVAEducation wants its users to help them learn in an easy way. For that purpose, you are free to prepare online MCQs and quizzes.
NVAEducation also facilitates users to contribute in online competitions with other students to make a challenging situation to learn in a creative way. You can create one to one, and group competition on an topic of a book/course code. Also on NVAEducation you can get certifications by passing the online quiz test.
Question 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?
Dynamic programming
Recursion
Brute force
Dynamic programming, Recursion and Brute force
Question 5: 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
Question 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?
nth catalan number
n factorial
n cube
n square
Question 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?
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];
Question 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]; }
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];
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];
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];
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];
Online Quizzes of gs122 Data Communication and Computer Network
Sorting - Insertion Sort - Quiz No.1
gs gs122
Data Communication and Computer Network Online Quizzes
Sorting - Insertion Sort - Quiz No.2
gs gs122
Data Communication and Computer Network Online Quizzes
Sorting - Insertion Sort - Quiz No.3
gs gs122
Data Communication and Computer Network Online Quizzes
Sorting - LSD Radix Sort - Quiz No.1
gs gs122
Data Communication and Computer Network Online Quizzes
Sorting - MSD Radix Sort - Quiz No.1
gs gs122
Data Communication and Computer Network Online Quizzes
Sorting - MSD Radix Sort - Quiz No.2
gs gs122
Data Communication and Computer Network Online Quizzes
