ObjectiveMcq
Print Protected
This page is protected for print. Use the website to view the content.
What is the time complexity of the above dynamic programming implementation of the assembly line scheduling problem?
O(1)
O(n)
O(n^{2})
O(n^{3})
The time complexity of the above dynamic programming implementation of the assembly line scheduling problem is O(n).
Which of the following lines should be inserted to complete the above code?
(t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i]))
(t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+spent[1][i]))
(t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]))
none of the mentioned
The line t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i]) should be added to complete the above code.
What is the minimum time required to build the car chassis?
40
41
42
43
The minimum time required is 43.
The path is S2,1 -> S1,2 -> S2,3 -> S2,4, where Si,j : i = line number, j = station number
For the optimal solution, which should be the exit assembly line?
Line 1
Line 2
All of the mentioned
None of the mentioned
For the optimal solution, the exit assembly line is line 2.
For the optimal solution which should be the starting assembly line?
Line 1
Line 2
All of the mentioned
None of the mentioned
For the optimal solution, the starting assembly line is line 2.
In the dynamic programming implementation of the assembly line scheduling problem, how many lookup tables are required?
0
1
2
3
In the dynamic programming implementation of the assembly line scheduling problem, 2 lookup tables are required one for storing the minimum time and the other for storing the assembly line number.
What is the time complexity of the brute force algorithm used to solve the assembly line scheduling problem?
O(1)
O(n)
O(n^{2})
O(2^{n})
In the brute force algorithm, all the possible ways are calculated which are of the order of 2^{n}.
Which of the following methods can be used to solve the assembly line scheduling problem?
Recursion
Brute force
Dynamic programming
All of the mentioned
All of the above mentioned methods can be used to solve the assembly line scheduling problem.
Which of the following lines completes the above code?
find_max(ans[itm - 1][w - wt[itm - 1]] + val[itm - 1], ans[itm - 1][w])
find_max(ans[itm - 1][w - wt[itm - 1]], ans[itm - 1][w])
ans[itm][w] = ans[itm - 1][w];
ans[itm+1][w] = ans[itm - 1][w];
find_max(ans[itm - 1][w - wt[itm - 1]] + val[itm - 1], ans[itm - 1][w]) completes the above code.
The 0-1 Knapsack problem can be solved using Greedy algorithm.
True
False
The Knapsack problem cannot be solved using the greedy algorithm.
What is the time complexity of the brute force algorithm used to solve the Knapsack problem?
O(n)
O(n!)
O(2^{n})
O(n^{3})
In the brute force algorithm all the subsets of the items are found and the value of each subset is calculated. The subset of items with the maximum value and a weight less than equal to the maximum allowed weight gives the answer. The time taken to calculate all the subsets is O(2^{n}).
Which of the following problems is equivalent to the 0-1 Knapsack problem?
You are given a bag that can carry a maximum weight of W. You are given N items which have a weight of {w1, w2, w3,...., wn} and a value of {v1, v2, v3,...., vn}. You can break the items into smaller pieces. Choose the items in such a way that you get the maximum value
You are studying for an exam and you have to study N questions. The questions take {t1, t2, t3,...., tn} time(in hours) and carry {m1, m2, m3,...., mn} marks. You can study for a maximum of T hours. You can either study a question or leave it. Choose the questions in such a way that your score is maximized
You are given infinite coins of denominations {v1, v2, v3,....., vn} and a sum S. You have to find the minimum number of coins required to get the sum S
You are given a suitcase that can carry a maximum weight of 15kg. You are given 4 items which have a weight of {10, 20, 15,40} and a value of {1, 2, 3,4}. You can break the items into smaller pieces. Choose the items in such a way that you get the maximum value
In this case, questions are used instead of items. Each question has a score which is same as each item having a value. Also, each question takes a time t which is same as each item having a weight w. You have to maximize the score in time T which is same as maximizing the value using a bag of weight W.
You are given a knapsack that can carry a maximum weight of 60. There are 4 items with weights {20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of the items you can carry using the knapsack?
160
200
170
90
The maximum value you can get is 160. This can be achieved by choosing the items 1 and 3 that have a total weight of 60.
Which of the following methods can be used to solve the Knapsack problem?
Brute force algorithm
Recursion
Dynamic programming
Brute force, Recursion and Dynamic Programming
Brute force, Recursion and Dynamic Programming can be used to solve the knapsack problem.
The Knapsack problem is an example of ____________
Greedy algorithm
2D dynamic programming
1D dynamic programming
Divide and conquer
Knapsack problem is an example of 2D dynamic programming.
Which of the following lines should be inserted to complete the above code?
val = mx_sm
return val
mx_sm = val
return mx_sm
The line "mx_sm = val" should be inserted to complete the above code.
The dynamic programming implementation of the maximum sum rectangle problem uses which of the following algorithm?
Hirschberg's algorithm
Needleman-Wunsch algorithm
Kadane's algorithm
Wagner Fischer algorithm
The dynamic programming implementation of the maximum sum rectangle problem uses Kadane's algorithm.
What is the time complexity of the brute force implementation of the maximum sum rectangle problem?
O(n)
O(n^{2})
O(n^{3})
O(n^{4})
The time complexity of the brute force implementation of the maximum sum rectangle problem is O(n^{4}).
Consider the 3×3 matrix {{2,1,-3},{6,3,4},{-2,3,0}}. What is the sum of the elements of the maximum sum rectangle?
13
16
14
19
The complete matrix represents the maximum sum rectangle and it's sum is 14.
Consider the 2×2 matrix {{-1,-2},{-3,-4}}. What is the sum of elements of the maximum sum rectangle?
0
-1
-7
-12
Since all the elements of the 2×2 matrix are negative, the maximum sum rectangle is {-1}, a 1×1 matrix containing the largest element. The sum of elements of the maximum sum rectangle is -1.
