Algorithms

Programming Assignment #3

Problem Description: Strategy Game

A new strategy video game has the player taking the role of the ruler of a weak state which

is under attack by a substantially stronger enemy. Initially the player controls all N cities of his

state. The state is long and thus the cities can be represented as N squares on a line as depicted

in Figure 1. At the end of each year the player receives from each city i he controls, pi gold coins

for taxes. The opponent eventually is going to conquer the whole state; thus, the objective for the

player is to maximize the amount of gold he collects before all the cities are overtaken.

At the beginning of every year the player decides to build a wall between two neighbor cities

he controls. Subsequently, the enemy observes the position of the wall and chooses to attack either

from east or west conquering all the cities before the wall. At the end of the year the player receives

taxes from the cities still under his control and the wall is destroyed. The same process is repeated

every year until the whole state is conquered.

The player should be particularly careful when choosing the location of the wall. It is known

that the enemy always decides to attack from the direction that minimizes the number of gold coins

the player can collect. That is, you may assume that the enemy minimizes the amount of coins the

player can receive (after she/he has chosen the location for the wall) in the current and all future

rounds.

Example: Consider N = 5 cities and p1 = 8, p2 = 6, p3 = 2, p4 = 4, p5 = 2. The best option

for the player is to build a wall between cities 2 and 3. The enemy attacks from west and conquers

cities 1 and 2 and that allows player to collect 8 gold coins (from cities 3, 4 and 5) at the end of

the year. At the beginning of the next year the player builds a wall between the cities 3 and 4.

The enemy attacks from east and conquers cities 4 and 5 allowing the player to collect 2 gold coins

(from city 3) at the end of the year. There are no more neighbor cities for the player to build a

wall thus the game is over with total amount of gold coins equal to 10.

Programming Assignment #3: December 6, 2019, 11:59pm 2

Figure 1: Strategy Game. If the enemy attacks from the west, cities 5 and 6 will remain under

player’s control and the profit for the current year will be p5 + p6. If the enemy attacks from the

east, cities 1,2,3 and 4 will remain under player’s control and the profit for the current year will be

p1 + p2 + p3 + p4.

Instructions

Implement a dynamic programming algorithm to find the maximum number of coins to be obtained given an array of cities. The first part of this assignment will be to generate your report before

you begin code implementation. This includes finding the recurrence formula and proving your algorithm’s complexity. The second part of this assignment will be your actual code implementation.

You will be given very little starter code in the form of Driver3.java and Assignment3.java, as

well as some small test cases. Your solution should be built in the maxCoinValue function given to

you in Assignment3.java. You may use Driver3.java as a means to test your code. Simply pass

the name of a text file (just city coin values separated by spaces) as an argument to test.

Part 1: Report [30 points]

Write a short report that includes the information below. There are reasonable O(n

3

), O(n

2

log n),

and O(n

2

) solutions. Faster run-time will give more points!

Note: You might find the O(n

2

) solution challenging to come up with.

Note: You can get full credit on the Code part of the assignment with a O(n

2

log n) solution.

(a) Explain what the dynamic programming subproblems are, and provide a recursive formula

for OPT.

(b) Provide a succinct argument of correctness, and explain and justify the complexity of your

algorithm.

Part 2: Code [70 points]

This part of your assignment will be graded both on correctness, and time-complexity.

• Given an int[] cities, it is your job to return the maximum coin value in function maxCoinValue.

Each index i in the array has an integer value corresponding to pi

. Your value range is as

follows, 1 ≤ pi ≤ 30000.

Programming Assignment #3: December 6, 2019, 11:59pm 3

• For the first 70% percent of the test case 2 ≤ N ≤ 500. (A properly implemented O(n

3

)

solution should suffice for these test cases.)

• For the next 30% percent of the test case 2000 ≤ N ≤ 2500. (Both O(n

2

) or O(n

2

log n)

should pass these test cases.)

• Be sure to practice good programming style, as poor style may result in a deduction of points

(e.g. do not name your variables foo1, foo2, int1, and int2).

Memory limit: 128MB

What To Submit

Failure to follow these instructions will result in a deduction of points. You should submit a

single zip file titled eid lastname firstname.zip that contains:

• Program3.java

• Your report in pdf form, named: eid lastname firstname.pdf.

DO NOT USE PACKAGE STATEMENTS. Your code will fail to compile in our grader if

you do and it won’t be regraded if your program fails to compile due to package imports.