7 practice sets · Page 1 of 1
Which line will complete the ABOVE code?
prices[j-1] + max_val[tmp_idx]
prices[j] + max_val[tmp_idx]
prices[j-1] + max_val[tmp_idx - 1]
prices[j] + max_val[tmp_idx - 1]
Correct Answer: A — prices[j-1] + max_val[tmp_idx]
Explanation:
prices[j-1] + max_val[tmp_idx] completes the code.
For every rod cutting problem there will be a unique set of pieces that give the maximum price.
True
False
Correct Answer: B — False
Explanation:
Consider a rod of length 3. The prices are {2,3,6} for lengths {1,2,3} respectively. The pieces {1,1,1} and {3} both give the maximum value of 6.
Complete the above code.
max_price, prices[i] + rod_cut(prices,len - i - 1)
max_price, prices[i - 1].
max_price, rod_cut(prices, len - i - 1)
max_price, prices[i - 1] + rod_cut(prices,len - i - 1)
Correct Answer: A — max_price, prices[i] + rod_cut(prices,len - i - 1)
Explanation:
max_price, prices[i] + rod_cut(prices,len - i - 1) completes the above code.
Which of these pieces give the maximum price?
{1,2,7}
{10}
{2,2,6}
{1,4,5}
Correct Answer: C — {2,2,6}
Explanation:
The pieces {2,2,6} give the maximum value of 27.
Consider the brute force implementation of the rod cutting problem in which all the possible cuts are found and the maximum value is calculated. What is the time complexity of this brute force implementation?
O(n^{2})
O(n^{3})
O(nlogn)
O(2^{n})
Correct Answer: D — O(2^{n})
Explanation:
The brute force implementation finds all the possible cuts. This takes O(2^{n}) time.
What is the maximum value that you can get after cutting the rod and selling the pieces?
10
11
12
13
Correct Answer: C — 12
Explanation:
The pieces {1,2 2} give the maximum value of 12.
Given a rod of length n and the selling prices of all pieces smaller than equal to n, find the most beneficial way of cutting the rod into smaller pieces. This problem is called the rod cutting problem. Which of these methods can be used to solve the rod cutting problem?
Brute force
Dynamic programming
Recursion
Brute force, Dynamic programming and Recursion
Correct Answer: D — Brute force, Dynamic programming and Recursion
Explanation:
Brute force, Dynamic programming and Recursion can be used to solve the rod cutting problem.
