Reference no: EM13317609

You and your eight-year-old nephew Elmo decide to play a simple card game. Atthe beginning of the game, the cards are dealt face up in a long row. Each card isworth a different number of points. After all the cards are dealt, you and Elmo taketurns removing either the leftmost or rightmost card from the row, until all the cardsare gone. At each turn, you can decide which of the two cards to take. The winner ofthe game is the player that has collected the most points when the game ends.Having never taken an algorithms class, Elmo follows the obvious greedy strategy-when it's his turn, Elmo always takes the card with the higher point value.Your task is to find a strategy that will beat Elmo whenever possible. (It might seemmean to beat up on a little kid like this, but Elmo absolutely hates it when grown-upslet him win.)(a) Prove that you should not also use the greedy strategy. That is, show that thereis a game that you can win, but only if you do not follow the same greedystrategy as Elmo.(b) Describe and analyze an algorithm to determine, given the initial sequence ofcards, the maximum number of points that you can collect playing against Elmo.(c) Five years later, Elmo has become a much stronger player. Describe andanalyze an algorithm to determine, given the initial sequence of cards, the maximum number of points that you can collect playing against a perfect opponent.