Dynamic Programming In Data Structures MCQs
Practice Dynamic Programming In Data Structures MCQs for competitive exams.
Dynamic Programming In Data Structures MCQs
Practice questions from this topic.
What is the space complexity of the following dynamic programming implementation of the balanced partition problem? #include int balanced_partition(int *arr, int len) { int sm = 0, i, j; for(i = 0;i < len; i++) sm += arr[i]; if(sm % 2 != 0) return 0; int ans[sm/2 + 1][len + 1]; for(i = 0; i <= len; i++) ans[0][i] = 1; for(i = 1; i <= sm/2; i++) ans[i][0] = 0; for(i = 1; i <= sm/2; i++) { for(j = 1;j = arr[j - 1]) ans[i][j] = ans[i][j] || ans[i - arr[j - 1]][j - 1]; } } return ans[sm/2][len]; } int main() { int arr[] = {3, 4, 5, 6, 7, 1}, len = 6; int ans = balanced_partition(arr,len); if(ans == 0) printf("false"); else printf("true"); return 0; }
Correct Answer: C
The following sequence is a fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, .... Which technique can be used to get the nth fibonacci term?
Correct Answer: D
What is the output of the following program? #include int max_num(int a,int b) { if(a> b) return a; return b; } int maximum_subarray_sum(int *arr, int len) { int sum[len], idx; sum[0] = arr[0]; for(idx = 1; idx < len; idx++) sum[idx] = max_num(sum[idx - 1] + arr[idx], arr[idx]); int mx = sum[0]; for(idx = 0; idx mx) mx =sum[idx]; return mx; } int main() { int arr[] = {-20, 23, 10, 3, -10, 11, -5},len = 7; int ans = maximum_subarray_sum(arr, len); printf("%d",ans); return 0; }
Correct Answer: B
Consider the following code to find the nth fibonacci term using dynamic programming: 1. int fibo(int n) 2. int fibo_terms[100000] //arr to store the fibonacci numbers 3. fibo_terms[0] = 0 4. fibo_terms[1] = 1 5. 6. for i: 2 to n 7. fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2] 8. 9. return fibo_terms[n] Which technique is used by line 7 of the above code?
Correct Answer: C
If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called . . . . . . . .
Correct Answer: C
Consider the two matrices P and Q which are 10 x 20 and 20 x 30 matrices respectively. What is the number of multiplications required to multiply the two matrices?
Correct Answer: D
Complete the following dynamic programming implementation of the longest increasing subsequence problem: #include int longest_inc_sub(int *arr, int len) { int i, j, tmp_max; int LIS[len]; // array to store the lengths of the longest increasing subsequence LIS[0]=1; for(i = 1; i < len; i++) { tmp_max = 0; for(j = 0; j < i; j++) { if(arr[j] tmp_max) ___________; } } LIS[i] = tmp_max + 1; } int max = LIS[0]; for(i = 0; i max) max = LIS[i]; return max; } int main() { int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9; int ans = longest_inc_sub(arr, len); printf("%d",ans); return 0; }
Correct Answer: A
What is the output of the following naive method used to find the maximum sub-array sum? #include int main() { int arr[1000] = {-2, -5, 6, -2, 3, -1, 0,-5, 6}, len = 9; int cur_max, tmp_max, strt_idx, sub_arr_idx; cur_max = arr[0]; for(strt_idx = 0; strt_idx < len; strt_idx++) { tmp_max = 0; for(sub_arr_idx = strt_idx; sub_arr_idx cur_max) cur_max = tmp_max; } } printf("%d",cur_max); return 0; }
Correct Answer: C
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; }
Correct Answer: D
What is the value stored in max_val[5] after the following program is executed? #include #include int rod_cut(int *prices, int len) { int max_val[len + 1]; int i,j,tmp_price,tmp_idx; max_val[0] = 0; for(i = 1; i <= len; i++) { int tmp_max = INT_MIN; // minimum value an integer can hold for(j = 1; j tmp_max) tmp_max = tmp_price; } max_val[i] = tmp_max; } return max_val[len]; } int main() { int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 5; int ans = rod_cut(prices, len_of_rod); printf("%d",ans); return 0; }
Correct Answer: A
What is the space complexity of the following dynamic programming implementation of the edit distance problem where "m" and "n" are the lengths of the two strings? #include #include int get_min(int a, int b) { if(a < b) return a; return b; } int edit_distance(char *s1, char *s2) { int len1,len2,i,j,min; len1 = strlen(s1); len2 = strlen(s2); int arr[len1 + 1][len2 + 1]; for(i = 0;i <= len1; i++) arr[i][0] = i; for(i = 0; i <= len2; i++) arr[0][i] = i; for(i = 1; i <= len1; i++) { for(j = 1; j <= len2; j++) { min = get_min(arr[i-1][j],arr[i][j-1]) + 1; if(s1[i - 1] == s2[j - 1]) { if(arr[i-1][j-1] < min) min = arr[i-1][j-1]; } else { if(arr[i-1][j-1] + 1 < min) min = arr[i-1][j-1] + 1; } arr[i][j] = min; } } return arr[len1][len2]; } int main() { char s1[] = "abcd", s2[] = "defg"; int ans = edit_distance(s1, s2); printf("%d",ans); return 0; }
Correct Answer: C
Given a one-dimensional array of integers, you have to find a sub-array with maximum sum. This is the maximum sub-array sum problem. Which of these methods can be used to solve the problem?
Correct Answer: D