You and Alice and Bob are driving to Tijuana for spring break in Bob’s car. You are savingyour money for the trip and so you want to minimize the cost of gas on the way. In order tominimize your gas costs you have compiled the following information. First Bob’s car can reliably travelmmiles on a tank of gas (but no further). Alice has compiledgas-station data from the web and has plotted every gas station along your route along withthe price of gas at that gas station. Specifically Alice has created a list ofngas station prices P[1, ...,n], from closest to furthest, and a list of n distances D[1, ...,n] between two adjacentgas stations (the first distance is the distance from Bob’s house to the first gas station). Gasstation numbernis the closest gas station to your hotel in Tijuana. For convenience Alicehas converted thecost of gas into price per mile traveled in Bob’s carand also computed the 5 distance d(i, j)=∑jk=i+1D[k] the distance from gas stationito gas stationjfor 0≤i
Bob ensures you will begin your journey with a full tank of gas. You have decided to minimizethe number of stops byalways filling the tank full whenever you stop. Also when you get toTijuana youwill fill up for the return trip

1. Express this problem formally with input and output conditions.
2. Alice and Bob have ideas on how to minimize the cost of gas but they dis- agree. Bob suggests driving to the furthest gas station within m miles and filling up there. Help Alice show that his algorithm is not optimal by giving a counter example.

3. Alice suggest that if a greedy algorithm won't work maybe dynamic program- ming could help. Help Alice by stating a self-reduction for this problem.
4. State a dynamic programming algorithm based off of your self-reduction that computes the minimum gas cost.
5. What is the worst case run time of your dynamic programming algorithm?
6. Use your algorithm to compute minimum cost for the following lists of gas stations, distances and gas tank capacity.

Prices (cents per mile) [17,14,21,14,17,22,11,16,17,12,30, 25, 27,24,22,15,24,23,15,21]
Distances (miles) [24,31,42,31,33, 12, 34,55,25, 34, 64,24,13,52,33, 23, 64,43,25,15]
Your car can travel 150 miles on a tank of gas.
7. Bob notices that in your solution you always fill up at the cheapest gas station in range. He still thinks a greedy algorithm will work and suggests always filling up at the cheapest gas station within range. Show that this algorithm is not correct either.