Consider a row of n coins of values v1, …, vn, 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. the goal is to maximize the total value of the coins collected. each player plays optimally.

1. give an example of a sequence of coins such that it is not optimal for the first player to start by picking the available coin of larger value. that is, the greedystrategy of always picking the larger coin is suboptimal. recall that n is even.

2. give an o(n2) dynamic programming algorithm to compute an optimal strategy for the first player. the first player should be able to make each move optimally in o(1) time. your algorithm should return the optimal strategy for the first player, not the final score.

3. define the subproblems you will use to solve this problem. define all variables you introduce.

4. write a recurrence expressing the optimal solution of the general subproblem in terms of optimal solutions of smaller subproblems. solve the base cases.

5. describe your algorithm in pseudocode. comment your code.

6. explain clearly and concisely why your algorithm is correct. restatements of steps of the algorithm will receive no credit.

7. analyze the running time of your algorithm, including the number of subproblems and the time spent per subproblem.

8. extend your algorithm to keep track of the optimal move at any point of the game.