Home / MCQ Bank / Computer
Computer Dynamic Programming In Data Structures Difficulty: Medium

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

Select the correct option to test your answer:

More Computer Questions

Which statements are true regarding ICMP packets? 1. They acknowledge receipt of a TCP segment. 2. They guarantee datagram delivery. 3. They can provide hosts with information about network problems. 4. They are encapsulated within IP datagrams. . . . . . . . . initiates an infinite loop right from the start. A graph is found to be 2 colorable. What can be said about that graph? What will be the output of the following Python code? l1=[1, 2, 3, [4]] l2=list(l1) id(l1)==id(l2) In which of the following scenarios is the Bellman-Ford algorithm preferred over Dijkstra's algorithm?