Driving an Electric Car Economically (30 Points)

8

You are about to drive an electric car from vour home to San Francisco. Your car runs on single-use batteries, which must be replaced after at most 100 miles. You will follow a fixed route; there are several fueling stations along the way, and each station charges a different price for installing a new battery. Before you start your trip, you carefully list the locations and prices of every fueling station along the way. Given this information, how do you decide the best places to stop for replacing the battery? You can replace the battery early (before 100 miles are reached), but you must still pay full price for each new battery to be installed.

More formally, suppose you are given two arrays DIl..n and C|1..n), where Dlil is the distance from the start of the trip to the ith station, and Cli] is the cost to replace your battery at the ith station. Assume that your trip starts and ends at fueling stations (so

D[1] = 0 and DIn] is the total length of your trip), and that your car starts with an empty

battery (so you must install a new battery at station 1).

1. Describe a greedy algorithm to find the minimum number of refueling stops (for replacing batteries) needed to complete your trip. Prove that your algorithm is correct. What is its cost?
2. But what you really want to minimize is the total cost of travel. Show that your greedy algorithm in part (a) does not produce an optimal solution when extended to this setting.

(c Describe an efficient algorithm to compute the locations of the fuel stations you should

stop at (for replacing the battery to minimize the total cost of travel.

Problem 4. Driving an Electric Car Economically ( 30 Points) You are about to drive an electric car from your home to San Francisco. Your car runs a fixed route; there are several fueling stataced after at most 100 miles. You will follow different price for installing a new battery. Before youg the way, and each station charges a you decide the brices of every fueling station along you start your trip, you carefully list the early (before 100 miles are to stop for replacing the battery? You can replace the battery to be installed. More formally, suppose you are given two arrays D[1n] and C[1n], where D[t] is the distance from the start of the trip to the ith station, and C[i] is the cost to replace your battery at the ith station. Assume that your trip starts and ends at fueling stations [so D[1]=0 and D[n] is the total length of yous D[1]=0 and D[n] is the total length of your trip), and that your car starts with an empry battery (so you must install a new battery at station 1 ). (a) Describe a greedy algorithm to find the minimum number of refueling stops (for replacing batteries) needed to complete your trip. Prove that your algorithm is correct. What is its cost? (b) But what you really want to minimize is the total cost of travel. Show that your greedy algorithm in part (a) does not produce an optimal solution when extended to this setting. (c) Describe an efficient algorithm to compute the locations of the fuel stations you should stop at (for replacing the battery) to minimize the total cost of travel