8. Road trip (II). Consider again Problem 2. Suppose at each mile post a0, a1, . . . , an there is a gas station. You start out with u units of gas in your gas tank at mile post a0 and you want to get to mile post an. Your cars gas tank has a capacity of c units of gas and your car gets R miles per unit of gas. You can stop at any mile post along the way and buy as much gas as you like. However, the following constraint must always be satisfied: The amount of gas in your tank should never go below 0 or above c. () (a) Suppose the goal is to plan your trip so that you make as few stops as possible along the way to buy gas. Consider the following simple greedy strategy: while you are not at the destination do fill up your tank at the current location drive to the farthest gas station you can reach on a full tank of gas Prove that this strategy results in an itinerary that minimizes the number of stops. Hint: prove by induction on n. (b) Now assume that the gas stations sell gas at different prices, and that the goal is to plan the trip to minimize the total amount of money you spend on gas. To this end, assume that gas costs pi > 0 dollars per unit of gas at mile post ai , for i = 0, . . . , n 1, and set pn := 0. Consider the following greedy strategy: while you are not the destination do (1) if you could reach a gas station with a cheaper price on a full tank of gas, then: buy the minimal amount of gas (possibly none) needed to the reach the first such station, and drive to it; (2) otherwise, fill up your tank and drive to the next gas station Prove that this greedy strategy is optimal. Hint: prove by induction on n. To do this, you might proceed as follows. Consider an input I = (u; a0, . . . , an; p0, . . . , pn; c, R), where n > 0, and a strategy X on input I. The goal is to show that X is no better than the greedy strategy. To do so, it is helpful to first transform X into a strategy that is somewhat similar to the greedy stategy. Specifically, in the first loop iteration of the greedy strategy, either case (1) or case (2) applies. For case (1), transform X into a strategy Y1 for input I that is at least as good as X, and which buys the same amount of gas at a0 as greedy, and does not buy any gas at the subsequent stations up to but not including the cheaper one. For case (2), transform X into a strategy Y2 for input I that is at least as good as X, and which buys the same amount of gas at a0 as greedy. After you do this, it should be straightforward to apply the induction hypothesis to a smaller input Ie, and conclude that X is no better than the greedy strategy on input I. See the general correctness proof strategy from the class notes on greedy algorithms. (c) Suppose that the greedy algorithm in part (b) is modified so that case (1) reads as follows: (1) if you could reach a gas station with a cheaper price on a full tank of gas, then: buy the minimal amount of gas (possibly none) needed to the reach the cheapest such station, and drive to it; Show that this strategy is not optimal. You should do this by providing an explicit counter-example.

8. Road trip (II). Consider again Problem 2. Suppose at each mile post ao, a1,... , an there is a gas station. You start out with u units of gas in your gas tank at mile post ao and you want to get to mile post an. Your car's gas tank has a capacity of c units of gas and your car gets R miles per unit of gas. You can stop at any mile post along the way and buy as much gas as you like. However, the following constraint must always be satisfied The amount of gas in your tank should never go below 0 or above c (a) Suppose the goal is to plan your trip so that you make as few stops as possible along the way to buy as Consider the following simple greedy strategy while you are not at the destination do fill up vour tank at the current locatiorn drive to the farthest gas station you can reach on a full tank of gas Prove that this strategy results in an itinerary that minimizes the number of stops Hint: prove by induction on n (b) Now assume that the gas stations sell gas at different prices, and that the goal is to plan the trip to minimize the total amount of money you spend on gas. To this end, assume that gas costs pi > 0 dollars per unit of gas at mile post ai, for i-0,... ,n - 1, and set pn:-0 Consider the following greedy strategy while you are not the destination do (1) if you could reach a gas station with a cheaper price on a full tank of gas, then buy the minimal amount of gas (possibly none) needed to the reach the first suclh station, and drive to it; (2) otherwise, fill up your tank and drive to the next gas station Prove that this greedy strategy is optimal Hint: prove by induction on n. To do this, you might proceed as follows. Consider an input I = (u;ao,..., aniPo,.. . ,pn; c, R), where n > 0, and a strategy X on input I. The goal is to show that X is no better than the greedy strategy. To do so, it is helpful to first transform X into a strategy that is somewhat similar to the greedy stategy. Specifically, in the first loop iteration of the greedy strategy, either case (1) or case (2) applies. For case (1), transform X into a strategy i for input I that is at least as good as X, and which buys the same amount of gas at ao as greedy, and does not buy any gas at the subsequent stations up to but not including the cheaper one. For case (2), transform X into a strategy Y2 for input I that is at least as good as X, and which buys the same amount of gas at ao as greedy. After you do this, it should be straightforward to apply the induction hypothesis to a smaller input I, and conclude that X is no better than the greedy strategy on input I. See the "general correctness proof strategy" from the class notes on greedy algorithms (c) Suppose that the greedy algorithm in part (b) is modified so that case (1) reads as follows (1) if you could reach a gas station with a cheaper price on a full tank of gas, then buy the minimal amount of gas (possibly none) needed to the reach the cheapest such station, and drive to it; Show that this strategy is not optimal. You should do this by providing an explicit counter-example 8. Road trip (II). Consider again Problem 2. Suppose at each mile post ao, a1,... , an there is a gas station. You start out with u units of gas in your gas tank at mile post ao and you want to get to mile post an. Your car's gas tank has a capacity of c units of gas and your car gets R miles per unit of gas. You can stop at any mile post along the way and buy as much gas as you like. However, the following constraint must always be satisfied The amount of gas in your tank should never go below 0 or above c (a) Suppose the goal is to plan your trip so that you make as few stops as possible along the way to buy as Consider the following simple greedy strategy while you are not at the destination do fill up vour tank at the current locatiorn drive to the farthest gas station you can reach on a full tank of gas Prove that this strategy results in an itinerary that minimizes the number of stops Hint: prove by induction on n (b) Now assume that the gas stations sell gas at different prices, and that the goal is to plan the trip to minimize the total amount of money you spend on gas. To this end, assume that gas costs pi > 0 dollars per unit of gas at mile post ai, for i-0,... ,n - 1, and set pn:-0 Consider the following greedy strategy while you are not the destination do (1) if you could reach a gas station with a cheaper price on a full tank of gas, then buy the minimal amount of gas (possibly none) needed to the reach the first suclh station, and drive to it; (2) otherwise, fill up your tank and drive to the next gas station Prove that this greedy strategy is optimal Hint: prove by induction on n. To do this, you might proceed as follows. Consider an input I = (u;ao,..., aniPo,.. . ,pn; c, R), where n > 0, and a strategy X on input I. The goal is to show that X is no better than the greedy strategy. To do so, it is helpful to first transform X into a strategy that is somewhat similar to the greedy stategy. Specifically, in the first loop iteration of the greedy strategy, either case (1) or case (2) applies. For case (1), transform X into a strategy i for input I that is at least as good as X, and which buys the same amount of gas at ao as greedy, and does not buy any gas at the subsequent stations up to but not including the cheaper one. For case (2), transform X into a strategy Y2 for input I that is at least as good as X, and which buys the same amount of gas at ao as greedy. After you do this, it should be straightforward to apply the induction hypothesis to a smaller input I, and conclude that X is no better than the greedy strategy on input I. See the "general correctness proof strategy" from the class notes on greedy algorithms (c) Suppose that the greedy algorithm in part (b) is modified so that case (1) reads as follows (1) if you could reach a gas station with a cheaper price on a full tank of gas, then buy the minimal amount of gas (possibly none) needed to the reach the cheapest such station, and drive to it; Show that this strategy is not optimal. You should do this by providing an explicit counter-example