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 ifrom the previous station s_i-1. The distance to the first gas station is d(s₁), and $0 < d(s_i) \leq n$ 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.