Problem 3. Strategery Alice and Bob play the following game. There is a row of n tiles with values a,an written on them. Starting with Alice, Alice and Bob take turns removing either the first or last tile in the row and placing it in their pile until there are no tiles remaining. For example, if Alice takes tile 1, Bob can take either tile 2 or tile n on the next turn. At the end of the game, each player receives a number of points equal to the sum of the values of their tiles minus that of the other player's tiles. Specifically, if Alice takes tiles A 1, , n} and Bob takes tiles B-1, , n} \ A, then their scores are -and Xa-^ iEA EB IEB respectively. For example, if n = 3 and the tiles have numbers 10,2,8 then taking the first tile guarantees Alice a score of at least 10 +2-8-4, whereas taking the last tile would only guarantee Alice a score of at least 8 2-10-0 In this question, you will design an algorithm to determine the maximum score that Alice can guarantee for herself, assuming Bob plays optimally to maximize his score. Note that the sum of their scores is always 0, so if Bob is playing o he is also playing optimally to m ptimally to maximize his own score, then inimize Alice's score. (a) Describe the set of subproblems that your dynamic programming algorithm will consider. Your solution should look something like "For every., we define OPT to be..." Solution: (b) Give a recurrence expressing the solution to each subproblem in terms of the solution to smaller subproblems. Solution: (c) Explain in English a valid order to fill your dynamic programming table in a "bottom-up" implementation of the recurrence. Solution: (d) Describe in pseudocode an algorithm that finds the maximum score that Alice can guaran- tee for herself. Your implementation may be either "bottom-up" or "top-down." Solution: (e) Analyze the running time and space usage of your algorithm. Solution