You and your eight-year-old nephew elmo decide to play a

Assignment Help Data Structure & Algorithms

Reference no: EM13380247

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 greedystrategy-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 greedy strategy 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 and analyze an algorithm to determine, given the initial sequence of cards, the maximum number of points that you can collect playing against a perfectopponent

Reference no: EM13380247

Questions Cloud

Wireless networksconsider a warehouse that is 60m by 30m : wireless networksconsider a warehouse that is 60m by 30m. wireless networking is required so that up to 20 staff

1 ascii code is a fixed-length coding scheme using the : 1. ascii code is a fixed-length coding scheme. using the 7-bit ascii code table 3 or any other references find the

The data encryption standard des is a symmetric-key : the data encryption standard des is a symmetric-key algorithm for the encryption of electronic data which you

From your study of asymmetric and symmetric key : from your study of asymmetric and symmetric key cryptography use your own words to compare between them in terms of1.

You and your eight-year-old nephew elmo decide to play a : you and your eight-year-old nephew elmo decide to play a simple card game. atthe beginning of the game the cards are

Write a paper discussing threads vs processes what is a : write a paper discussing threads vs processes. what is a thread? what is a process? how are they different? how are

Write two page paper describing xml and json what are they : write two page paper describing xml and json. what are they? why do we need them? are there certain applications that

1 with what kind of network device router or switch do you : 1 with what kind of network device router or switch do you replace device 1 device 2 and device 3? and why? notenbsp

Study carefully the following network topology it is : study carefully the following network topology. it is required that the small business smart office services pty ltd

User Account

All Pages