2.4 CHALLENGE You and your friends are driving to Tijuana for spring break. You are saving your money for the trip and so you want to minimize the cost of gas on the way. In order to minimize your gas costs you and your friends have compiled the following information First your car can reliably travel m miles on a tank of gas (but no further. One of your friends has mined gas-station data off the web and has plotted every gas station along your route along with the price of gas at that gas station. Specifically they have created a list of n+1 gas station prices from closest to furthest and a list of n distances between two adjacent gas stations. Tacoma is gas station number 0 and Tijuana is gas station number . For convenience they have converted the cost of gas into price per mile traveled in your car. In addition the distance in miles between two adjacent gas-stations has also been calculated. You will begin your journey with a full tank of gas and when you get to Tijuana you will fill up for the return trip You need to determine which gas stations to stop at to minimize the cost of gas on your trip. 1. 2. 3. (1 point) Express this problem formally with input and output conditions. (2 points) State a self-reduction for your problem. (2 points) State a dynamic programming algorithm based off of your self reduction that computes the minimum gas cost. 1. (2 points) Design a function that recovers the gas stations that should be stopped at to achicve the minimum cost. 5. (1 point) Use your algorithm to compute minimum cost and the right gas stations for the following lists of gas stations, distances and gas tank capacity. Prices (cents per mile) [12,14,21,14,17,22,11,16, 17,12,30,25,27,24,22,15,24,23,15,21] Distances (miles) 31,42,31,33,12,34,55,25,34,64,24,13,52,33,23,64, 43,25, 15] Your car can travel 170 miles on a tank of gas, 6. (2 points) What are the worst case time and space requirements of your complete solution? 2.4 CHALLENGE You and your friends are driving to Tijuana for spring break. You are saving your money for the trip and so you want to minimize the cost of gas on the way. In order to minimize your gas costs you and your friends have compiled the following information First your car can reliably travel m miles on a tank of gas (but no further. One of your friends has mined gas-station data off the web and has plotted every gas station along your route along with the price of gas at that gas station. Specifically they have created a list of n+1 gas station prices from closest to furthest and a list of n distances between two adjacent gas stations. Tacoma is gas station number 0 and Tijuana is gas station number . For convenience they have converted the cost of gas into price per mile traveled in your car. In addition the distance in miles between two adjacent gas-stations has also been calculated. You will begin your journey with a full tank of gas and when you get to Tijuana you will fill up for the return trip You need to determine which gas stations to stop at to minimize the cost of gas on your trip. 1. 2. 3. (1 point) Express this problem formally with input and output conditions. (2 points) State a self-reduction for your problem. (2 points) State a dynamic programming algorithm based off of your self reduction that computes the minimum gas cost. 1. (2 points) Design a function that recovers the gas stations that should be stopped at to achicve the minimum cost. 5. (1 point) Use your algorithm to compute minimum cost and the right gas stations for the following lists of gas stations, distances and gas tank capacity. Prices (cents per mile) [12,14,21,14,17,22,11,16, 17,12,30,25,27,24,22,15,24,23,15,21] Distances (miles) 31,42,31,33,12,34,55,25,34,64,24,13,52,33,23,64, 43,25, 15] Your car can travel 170 miles on a tank of gas, 6. (2 points) What are the worst case time and space requirements of your complete solution