Consider the following card game between two players. The dealer deals n cards f

Question

Consider the following card game between two players. The dealer deals n cards face up in a row. Each card has a value visible to both players. The players move in sequence. Each player, at her turn, can pick either the rightmost or the leftmost of the remaining cards on the table. The game ends when no cards are left. The goal of each player is to accumulate as much value as possible. For example, suppose that n = 5 and the cards have values 3, 2, 1, 7, 4 in order from left to right. Then suppose the players pick the cards in the order 4, 7, 3, 2, 1, where boldface indicates the first player’s picks, and the remainder the second player’s picks. Then the first player gets total value 4 + 3 + 1 = 8 and the second gets value 7+2 = 9. On the other hand, if the players pick the cards in the order 3, 4, 7, 2, 1, then the first player gets total value 3+ 7+ 1 = 11 and the second gets value 4+ 2 = 6. One can check that the first player can guarantee no better than 8 when picking 4 as the first card. So, the first player should start by picking the leftmost card with value 3. Design and analyze O(n 2 ) time algorithm for computing the optimal strategy for the first player. In particular, given a list of values, your algorithm should output whether the first player should pick the leftmost or the rightmost card in order to maximize her total value. Assume that the second player also plays optimally. We recommend using dynamic programming for this problem. Your submission should contain the following parts. (1) Clearly define a recursive function and provide the recursive equations for the function. (2) Give a brief informal argument justifying your recursive equation. We do not need a formal proof. (3) Provide an algorithm based on the recursive equation. (4) Argue the running time of your algorithm.

Explanation / Answer

The dynamic algorithm for the above card game having time O(n^2) and space O(n) is given by,

Consider the list L having A(i,l) and B(i,l) as first and second player scores

If the fist player wants to maximize his score

Then the second player gets the cards which first player had left

The result will be

A(1, length(L) )

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.