Algorithms

CSE 3500

Algorithms and Complexity

Homework 3 (optional)

February 27, 2015

This is a relatively short optional assignment, as there will be a new required assignment going out

the day this is due. These problems should be fairly straightforward, reasonable for practice. If you

want this practice to be valuable, solve these problems before looking for them on line.

1. Suppose you want to drive from Storrs to Key West, and (given your desire to escape winter as

quickly as possible) you want to stop for gas as few times as possible. You are given a route, and

an unsorted list of every gas station on that route. For each gas station you know how many miles

it is from Storrs on your route.

Using your knowledge from CSE 3500, you come up with the following greedy algorithm to choose

your stops: start with a full tank in Storrs; whenever you fill the tank, you choose the furthest gas

station that is within your car’s range on one tank (assume that distance is fixed); that is, the last

station you reach before you run out of gas. Drive to that station, and fill up. Keep doing this until

you fill your tank within your one-tank range of Key West, at which point you drive into Key West.

(a) Prove that this algorithm produces an optimal schedule, that is, there is no schedule that has

fewer gas stops on your route.

Solution: We will show that this algorithm is optimal because it always “stays ahead” of

any other schedule. First, we will show that this algorithm always “stays ahead” of any

other schedule.

Define s1 , s2 , . . . , sn as the set of gas stations sorted by distance from Storrs in ascending

order, d(si ) is the distance of the ith gas station. The distance to Key West is known, and is

greater than or equal to the distance to the furthest gas station. Let R be the distance that

your car drives on one tank of gas. A schedule is a list of gas stations visited in order; to

be practical a the distance between any consecutive gas stations must be...