Submitted by: Submitted by huda13
Views: 10
Words: 1361
Pages: 6
Category: Science and Technology
Date Submitted: 07/11/2015 09:35 PM
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...