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(si) is the distance of station ifrom the previous station si-1. The distance to the first gas station is d(s1), 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.