4 Homework 3

Deliverables. You should solve the problems in this homework using dynamic program- ming. Recall that a dynamic programming solution MUST include

1. A definition of subproblems

2. A recursion, including a base case

3. A bound on the number of subproblems (as in: the number of subproblems is O(n2k))

4. A bound on the recursion time (as in: the recursion takes time O(n)) Unless explicitly stated otherwise, pseudocode and examples are not required.

Problem 4.1. (Difficulty 3) There are n gold coins placed at positions {1, . . . , n} on a line.

The gold coin at position i has a positive weight wi. You can pick any of the n coins, except that if you pick the gold coin at position i then you cannot pick the adjacent ones, that is, the ones at positions i 1 and i + 1. Design a dynamic programming algorithm to compute the maximum total weight of the coins you can collect. Also explain how to compute the sequence of coins to be taken. Make your algorithm as fast as you can.

For example, if n = 3 and the gold coins have weights w1 = 20, w2 = 30, w3 = 15, then the maximum total weight is 20 + 15 = 35 and is obtained by picking the coins at positions 1 and 3.

Problem 4.2. (Difficulty 3) Bob has to plan his working life for the next T years. There are m jobs that Bob can do, and every year Bob must do exactly one job. Each job pays different amounts depending on the year. (For example, being a mail carrier will pay less and less with time, while being a computer scientist will pay more and more with time.) Specifically, during a year t a job j pays W (j, t). Bob is currently doing job 1 and can switch job at most S times.

Give an algorithm to compute the maximum possible earning of Bob for the next T years.

The running time of the algorithms should be polynomial in T , m, and S.

Problem 4.3. (Difficulty 3) [Taken from Jeff Erickson’s book] Vankin’s Mile is an American solitaire game played on an n n square grid. The player starts by placing a token on any square of the grid. Then on each turn, the player moves the token either one square to the right or one square down. The game ends when player moves the token off the edge of the board. Each square of the grid has a numerical value, which could be positive, negative, or zero. The player starts with a score of zero; whenever the token lands on a square, the player adds its value to his score. The object of the game is to score as many points as possible.For example, given the grid below, the player can score 8 6 + 7 3 + 4 = 10 points by placing the initial token on the 8 in the second row, and then moving down, down, right, down, down. (This is not the best possible score for this grid of numbers.)

1. Describe and analyze an efficient algorithm to compute the maximum possible score for a game of Vankin’s Mile, given the n × n array of values as input.

2.In the European version of this game, appropriately called Vankin’s Kilometer, the player can move the token either one square down, one square right, or one square left in each turn. However, to prevent infinite scores, the token cannot land on the same square more than once. Describe and analyze an efficient algorithm to compute the maximum possible score for a game of Vankin’s Kilometer, given the n n array of values as input.