# Question

Suppose that you are given an n × n checkerboard and a checker. You must move the checker from the bottom edge of the board to the top edge of the board according to the following rule. At each step you may move the checker to one of three squares:

1. The square immediately above,

2. The square that is one up and one to the left (but only if the checker is not already in the leftmost column),

3. The square that is one up and one to the right (but only if the checker is not already in the rightmost column). Each time you move from square x to square y, you receive p(x, y) dollars. You are given p(x, y) for all pairs (x, y) for which a move from x to y is legal. Do not assume that p(x, y) is positive. Give an algorithm that figures out the set of moves that will move the checker from somewhere along the bottom edge to somewhere along the top edge while gathering as many dollars as possible. Your algorithm is free to pick any square along the bottom edge as a starting point and any square along the top edge as a destination in order to maximize the number of dollars gathered along the way. What is the running time of your algorithm?

1. The square immediately above,

2. The square that is one up and one to the left (but only if the checker is not already in the leftmost column),

3. The square that is one up and one to the right (but only if the checker is not already in the rightmost column). Each time you move from square x to square y, you receive p(x, y) dollars. You are given p(x, y) for all pairs (x, y) for which a move from x to y is legal. Do not assume that p(x, y) is positive. Give an algorithm that figures out the set of moves that will move the checker from somewhere along the bottom edge to somewhere along the top edge while gathering as many dollars as possible. Your algorithm is free to pick any square along the bottom edge as a starting point and any square along the top edge as a destination in order to maximize the number of dollars gathered along the way. What is the running time of your algorithm?

## Answer to relevant Questions

Suppose that instead of always selecting the first activity to finish, we instead select the last activity to start that is compatible with all previously selected activities. Describe how this approach is a greedy ...Give a dynamic-programming solution to the 0–1 knapsack problem that runs in O (n W) time, where n is number of items and W is the maximum weight of items that the thief can put in his knapsack.Consider an ordinary binary min-heap data structure with n elements that supports the instructions INSERT and EXTRACT-MIN in O (lg n) worst-case time. Give a potential function Φ such that the amortized cost of INSERT ...Suppose we change line 4 of Dijkstra' s algorithm to the following. 4 while |Q| > 1. This change causes the while loop to execute |V | - 1 times instead of |V | times. Is this proposed algorithm correct?Give some examples of types for which it might be useful to define two or more distinct possible representations. Can you think of an example where distinct possible representations for the same type have different numbers ...Post your question

0