CSE 5311 Fall 1999

**Quiz #5**

- 1.
- Professor Midas drives an automobile between two cities
*m*miles apart along an interstate highway. His car can go*n*miles on a tank of gas, and he starts with a full tank. His map indicates that there are*g*gas stations along the way, and*d*(*s*_{i}) is the distance of station*i*from the previous station*s*_{i-1}. The distance to the first gas station is*d*(*s*_{1}), and for all*i*. The professor wishes to minimize the number of gas stops during the trip.- (a)
- (8 points.)
Prove that this road-trip problem exhibits optimal substructure.

- (b)
- (12 points.) Describe a greedy algorithm for solving the road-trip problem and prove that your algorithm yields an optimal solution.