You are going on a long trip You start on the road at mile p

You are going on a long trip. You start on the road at mile post 0. Along the way there are n hotels, at mileposts a₁ < a₂ < · · · < a_n, where each a_i is measured from the starting point. The only places you are allowed to stop are at these hotels, but you can choose which of the hotels you stop at. You must stop at the final hotel (at distance a_n), which is your destination.

You’d ideally like to travel 200 miles a day, but this may not be possible (depending on the spacing of the hotels). If you travel x miles during a day, the penalty for that day is (200 x)². You want to plan your trip so as to minimize the total penalty - that is, the sum, over all travel days, of the daily penalties.

a) Describe the structure of the subproblem

b) Find a recurrence for the optimal value of the subproblem in terms of smaller subproblems

Solution

Let Ci be the minimum cost in which to break your travel up, assuming that your last stop is hotel i. Let\'s let hotel 0 denote our starting point. As a basis, let C0 = 0. In general, to compute Ci, we consider all possible places k, 0 k < i, that we might have stopped the night before. The cost of having k as the previous stop is the minimum cost of getting to hotel k, followed by the cost of traveling in one day from k to i, a distance of (ai ak). Minimizing over all k gives the following rule: Ci = min 0 k < i Ck + (200 (ai ak ))2 A dynamic programming problem simply loops through all i (from 1 to n), building a linear array for the Ci values using the recurrence to calculate Ci from C0; . . . ; Ci1. Cn is the minimum cost we\'re looking for. If, in the table, for each values of i we also ll in the value of k which minimizes Ci, we can recreate the actual hotels we should stop at. It takes linear time to calculate each value of Ci, for a total time of O(n2 ). For part a), you got at least 10 points if you could write out the recurrence relation, plus or minus minor errors (wrong base case, incorrect minimizing bounds, informal but clear description). Some credit was given for an incorrect formalization, as long as it was a recurrence relations. Common mistakes included: not minimizing over a varying number of possibilities, using Ci1 in the place of Ck, and assuming you already knew the list of optimal stops to compute Ci. There was also some confusion as to where the recurrence should begin, at i = n or i = 1. The problem is symmetric. Therefore if you de ned Ci with your base case at Cn, you were not penalized but your de nition of Ci had to be consistent (i.e. you could not use Ci1 to de ne Ci, since the recursion would never stop). If you decided to use a di erent critter with more than one index and de ned it correctly, you were not penalized for that. However, your answer to part b) had to be consistent in any case with your answer to part a). That is if you were using a one-dimensional critter in a), you were expected to describe a one-dimensional array in b). For part b), if you mentioned that you needed a one-dimensional array you were given 3 points. Saying that the Ci\'s had to be computed in increasing order received another 3 points. If you got to that point then the remaining 4 points were for mentioning that dynamic programming allowed you to work through the subproblems only once and reuse your work. A very common mistake here was mentioning the need for a two-dimensional table (costs from any hotel to any hotel) after de ning a critter with only one index in part a). This received no credit since the table described was irrelevant to the problem. Another common error was to build a table from any hotel to any hotel for the cost function, which can always be calculated as the need arises. Again, since the table was irrelevant, no credit was awarded. you had to answer consistently with your previous answers. If you described an O(n3 ) algorithm in a) and b), and then answered O(n2 ), you were awarded no credit. If you just wrote down the answer with no explanation, or if you gave a correct explanation but a wrong answer, you were given 2 points. If you could write down the order of entries in the array, or the order of each computation in the array, that was also worth 2 points.