9 practice sets · Page 1 of 1
What is the space complexity of the above dynamic programming implementation of the assembly line scheduling problem?
O(1)
O(n)
O(n^{2})
O(n^{3})
Correct Answer: B — O(n)
Explanation:
The space complexity of the above dynamic programming implementation of the assembly line scheduling problem is O(n).
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})
Correct Answer: B — O(n)
Explanation:
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
Correct Answer: A — (t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i]))
Explanation:
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
Correct Answer: D — 43
Explanation:
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
Correct Answer: B — Line 2
Explanation:
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
Correct Answer: B — Line 2
Explanation:
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
Correct Answer: C — 2
Explanation:
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})
Correct Answer: D — O(2^{n})
Explanation:
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
Correct Answer: D — All of the mentioned
Explanation:
All of the above mentioned methods can be used to solve the assembly line scheduling problem.
