1. Suppose you have n coins in a row, and the kth coin in the row has the value vk. You play a 2-player game, where each player takes turns removing a single coin: either the first or last coin in the row. For example, suppose we have 5 coins in the row, and the values are v1 = 5, v2 = 10, v3 = 15, v4 = 5, v5 = 10. On your first turn, you could take coin 1, giving you a value of 5, or coin 5, giving you a value of 10. Then, your opponent could take one from either end (either 1,4 or 2,5, depending on your first move). The best you can do is to take coin 5 (+10), your opponent will then take coin 1 (+5), you then take coin 2 (+10), your opponent takes coin 3 (+15), and then you take coin 4 (+5). This leaves you with a value of 25 and your opponent with a value of 20. Given an arbitrary number of coins n and a list v1...vn of values, give a dynamic programming algorithm to determine the maximum value that you can get in this game, assuming you go first.

2. Suppose you have n identical glass balls. There is a building which is d floors high. There is a floor k, where if you drop a ball from floor k or higher, it will shatter, and if you drop a ball from below floor k, it will not shatter. An unbroken ball can be dropped multiple times. Devise a dynamic programming algorithm which will determine the minimum number of drops necessary to locate floor k. Analyze its runtime. 1 (For example, when there is one ball, you must try every floor one at a time. However, when you have a second ball, you might start higher up the building, then go back down if it breaks.)