QUESTION 4 (20 Marks) Assume we have a row of n coins of respective values v1, v2,... , vn The number of coins n is an even number larger than or equal to 2. Two players, Player 1 and Player 2, play a game by alternating turns. In each turn, one player can remove the leftmost (first) or righmost (last) coin from the row. The objective is to get the maximum amount of money at the end of the game. We assume that Player 1 plays first and we want to determine a strategy for Player 1 to collect the maximum amount of money. We assume that Player 2 is always going to play the best move she can (she wants to minimise the amount of money Player is going to collect). a. (3 marks) Write a formal Problem Statement for the previous optimisation problem. b. (5 marks) Professor Zundap points out that for the case where we have 2 coins, picking the larger one gives the maximum amount for Player 1. He thus concludes that a greedy strategy for Player 1, that is, picking the larger of the two end coins, will enable him to always collect the maximum amount of money even with more than 2 coins. Provide a counter-example to show that this greedy choice does not always maximise the amount Player 1 can collect. A strategy for Player 1, is a sequence of removal choices such as right, left, left. An optimal strategy for Player 1 is one that maximises Player I's amount at the end of the game. (*c. (8 marks) Propose an algorithm to compute an optimal strategy for Player d. (4 marks) What is the optimal strategy for Player 1 if we start with the following row of coins: 2, 8, 15,3, 7,10? QUESTION 4 (20 Marks) Assume we have a row of n coins of respective values v1, v2,... , vn The number of coins n is an even number larger than or equal to 2. Two players, Player 1 and Player 2, play a game by alternating turns. In each turn, one player can remove the leftmost (first) or righmost (last) coin from the row. The objective is to get the maximum amount of money at the end of the game. We assume that Player 1 plays first and we want to determine a strategy for Player 1 to collect the maximum amount of money. We assume that Player 2 is always going to play the best move she can (she wants to minimise the amount of money Player is going to collect). a. (3 marks) Write a formal Problem Statement for the previous optimisation problem. b. (5 marks) Professor Zundap points out that for the case where we have 2 coins, picking the larger one gives the maximum amount for Player 1. He thus concludes that a greedy strategy for Player 1, that is, picking the larger of the two end coins, will enable him to always collect the maximum amount of money even with more than 2 coins. Provide a counter-example to show that this greedy choice does not always maximise the amount Player 1 can collect. A strategy for Player 1, is a sequence of removal choices such as right, left, left. An optimal strategy for Player 1 is one that maximises Player I's amount at the end of the game. (*c. (8 marks) Propose an algorithm to compute an optimal strategy for Player d. (4 marks) What is the optimal strategy for Player 1 if we start with the following row of coins: 2, 8, 15,3, 7,10
