2. (12 marks) Suppose that you are taking a long bicycle trip on a trail. You are trying to get from the location at kilometre 0 on the trail to the location at kilometre n.

There are camping sites at various locations (x1 < x2 < < xm) along the trail. You will stop at one of those sites at the end of each day.

You know that you are able to travel at most r kilometres in a single day.

The goal is to find the sequence of stops that you should make at campsites at the end of each day, minimizing the total number of days.

(You can assume for this question that we are only talking about configurations for which a valid sequence actually exists.)

For example, if n = 800, if r = 200, and if the camping sites are at positions 125, 175, 275, 325, 400, 450, 625, 675, then two optimal paths (not necessarily the only optimal paths) are 0 125 275 450 625 800 and 0 175 325 450 625 800 (5 days each).

(a) Describe a greedy algorithm for how you should decide on a sequence of stopping points on your trip. [Do not refer to the specific numbers given in the example above, but use the general description of the problem (n, r, x1, x2, , xm).]

(b) Use a proof by contradiction to prove that, by using your greedy algorithm, you will never get stuck (stopping at a particular location and then unable to reach a new location on the next day). [Again, do not use the specific numbers provided in the example above, but use the general description of the problem (n, r, x1, x2, , xm). You can use the assumption mentioned above that a valid sequence actually does exist.]

[Hint: Suppose that you have stopped at some location xk, but then are unable to make a valid next move. What would that tell you about xk+1 xk? How does that help you to find a contradiction?]

(c) Use a proof by contradiction to prove that the path chosen by the greedy algorithm is optimal.

[Hint: Suppose that the greedy solution is not optimal. Suppose that g1, , gp are the locations chosen by the greedy algorithm, and let a1, , aq be the locations in an optimal solution that agrees with the greedy solution for the longest of all optimal solutions. (This will be quite similar to a proof done in class.)]