Suppose you have just purchased a new type of hybrid car that uses fucl extremely efficiently,...

 

Transcribed Image Text:

Suppose you have just purchased a new type of hybrid car that uses fucl extremely efficiently, but can only travel 100 miles on a single battery. The car's fuel is stored in a single-use battery, which must be replaced after at most 100 miles. The actual fuel is virtually free, but the batteries are expensive and can only be installed by licensed battery-replacement technicians. Thus, even if you decide to replace your battery early, you must still pay full price for the new battery to be installed. Moreover, because these batteries are in high demand, no one can afford to own more than one battery at a time. Suppose you are trying to get from San Francisco to New York City on the new Inter Continental Super-Highway, which runs in a direct line between these two cities. There are several fueling stations along the way; each station charges a different price for installing a new battery. Before you start your trip, you carefully print the Wikipedia page listing the locations and prices of every fueling station on the ICSH. Given this information, how do you decide the best places to stop for fuel? More formally, suppose you are given two arrays D[1..n] and C[1..n], where D[i] is the distance from the start of the highway 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 D[n] 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). • Describe and analyze a greedy algorithm to find the minimum number of refueling stops needed to complete your trip. Don't forget to prove that your algorithm is correct. • 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. • Describe an efficient algorithm to compute the locations of the fuel stations you should stop at to minimize the total cost of travel. Suppose you have just purchased a new type of hybrid car that uses fucl extremely efficiently, but can only travel 100 miles on a single battery. The car's fuel is stored in a single-use battery, which must be replaced after at most 100 miles. The actual fuel is virtually free, but the batteries are expensive and can only be installed by licensed battery-replacement technicians. Thus, even if you decide to replace your battery early, you must still pay full price for the new battery to be installed. Moreover, because these batteries are in high demand, no one can afford to own more than one battery at a time. Suppose you are trying to get from San Francisco to New York City on the new Inter Continental Super-Highway, which runs in a direct line between these two cities. There are several fueling stations along the way; each station charges a different price for installing a new battery. Before you start your trip, you carefully print the Wikipedia page listing the locations and prices of every fueling station on the ICSH. Given this information, how do you decide the best places to stop for fuel? More formally, suppose you are given two arrays D[1..n] and C[1..n], where D[i] is the distance from the start of the highway 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 D[n] 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). • Describe and analyze a greedy algorithm to find the minimum number of refueling stops needed to complete your trip. Don't forget to prove that your algorithm is correct. • 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. • Describe an efficient algorithm to compute the locations of the fuel stations you should stop at to minimize the total cost of travel.

Answer rating: 100% (QA)

a Greedy Algorithm The greedy algorithm works as follows 1 Sort the fueling stations by their distances Di in increasing order 2 Starting from the fir... View the full answer