Q(3) Consider a row of n coins of values v(1)... v(n), where n is even. We play
ID: 3740305 • Letter: Q
Question
Q(3) Consider a row of n coins of values v(1)... v(n), where n is even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the possible amount of money we can definitely win if we move first. Note: your opponent is intelligent as you are and he always takes the maximum option. Consider the following row of 4 coins: 392 1) Give an example of why the greedy algorithm of picking the max value in each turn is not optimal for you 2) Formulating the DP recursive sub-problems Suppose we have coins lined up from C to C with the values of Vi to Vj respectively. Let MV(l,j) the maximum value a player can collect from i 'th coin toj "th coin. Note that in every turn a player has two options: - Either pick the ith coin (from starting OR pick the jth coin (from the end) a. What is the recursive formula of MVi.j) for a player picking either coin i or j in every turn? b. Use your recursive formulas to solve the example given above of n-4 Note: Consider the cases when i-j and when i + 1 which are both base cases. 3) What is the running time of your algorithm?Explanation / Answer
1. A counter example of why greedy algorithm of picking the maximum value in each turn is
not optimal:
Consider the same example of 4 coins: 3, 9, 1, 2.
If you pick the max value coin at this point, you'll get 3.
And now the list of coins open to opponent is: 9, 1, 2.
He'll pick the max value coin at this point, which means he picks 9 which is more than
the sum of all the other 3 coins, and there by your opponent makes better amount than you by the end.
In this case, if you go greedily by picking max value every time, you'll make 3 + 2 = 5,
however, your opponent makes 9 + 1 = 10.
2. MV(i, j) = the maximum value a player can collect from i'th to j'th coin.
a. Recursive formula is:
MV(i, j) = max(Vi + min(MV(i+1, j-1), MV(i+2, j))
Vj + min(MV(i+1, j-1), MV(i, j-2))) if, j - i > 1
= Vi if i = j.
= max(Vi, Vj) if i+1 = j
b. Use your recursive formula, to solve the example given above of n = 4.
i = 1, j = 4.
MV(1, 4): max(V1 + min(MV(2, 3), MV(3, 4))
V4 + min(MV(2, 3), MV(1, 2)))
MV(2, 3): max(V2, V3) = 9.
MV(3, 4): max(V3, V4) = 2.
MV(1, 2): max(V1, V2) = 9.
Therefore, MV(1, 4): max(3 + min(9, 2), 2 + min(9, 9)) = max(3 + 2, 2 + 9) = max(5, 11) = 11.
3. Running time of your algorithm: T(n) = 4T(n-2) + 1
= 4^2 * T(n-2^2) + 1 + 4
= ... = 4^i * T(n-2^i) + 1 + 4 + 16 + ... + 4^(i-1)
= ... = O(n^2)?
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.