Determine the maximum possible value for the first player

Assignment Help Basic Computer Science

Reference no: EM13308474

Consider the following game. There is a sequence c1 ..cn of coins, where each coin ci has value ci.

Then two players take turns picking a coin from the sequence, but can only pick the first or the last coin of the (remaining) sequence. The goal is to collect coins of the largest total value. For this problem, n is even.

Give an efficient algorithm to determine the maximum possible value for the first player (assuming player two plays optimally), and analyze the running time. Solved by dynamic programming

Reference no: EM13308474

Questions Cloud

Find what was the pan evaporation rate in inches per day : Over the course of 3days, she added another 6lbs of water and at the end of 3days, there was 67lbs of water remaining. A nearby rain gage recorded 0.4 inches of precipitation over the period.

At what speed is the moon traveling : The moon is 3.85Ã-10^8 m from Earth, and it takes 27.3 days to orbit Earth. At what speed is the moon traveling relative to Earth

Choose three macroeconomic variables to include in discussio : Suppose the U.S. economy is in a recession which came from a negative AD shock. To provide consumers with an incentive to spend more of their disposable incomes, Congress and the President pass a law making it illegal for an individual to hold more ..

What pressure in psi is applied to water to reduce volume : At normal atmospheric conditions, approximately what pressure in psi must be applied to water 70 F to reduce its volume by 2 %

Determine the maximum possible value for the first player : Then two players take turns picking a coin from the sequence, but can only pick the first or the last coin of the (remaining) sequence. The goal is to collect coins of the largest total value. For this problem, n is even.

Create a data file in the specified format : Create a data file in the specified format. Write a script that would read from the file floatnums.dat into a matrix, round the numbers, and write the matrix in the desired format to a new file called "intnums.dat."

Determine is there any runoff from the area during the storm : During a 5 hour storm event, the precipitation over a 230-acre area is 1.5niches. There is constant infiltration at a rate of 0.12 inches/hour and the depession storage is 17 acre-ft. Is there any runoff from the area during the storm

How much volume of naoh solution is needed at poh at 9 : A NaOH solution has pOH at 8. How much volume of this NaOH solution is needed to prepare 1 L of a NaOH solution at pOH at 9.

Elaborate and apply to current events : Elaborate and apply to current events. Be sure to cite and demonstrate mastery.

User Account

All Pages