4. (2% points) You are driving on a straight road from point s to point t in a car that can run for D miles on a full tank. There are n gas stations on the road and their locations with respect to the starting location s are given to you. You want minimize the number of stops that you need to make (for filling gas) for reaching from s to t. Assume that you have a full tank at start s. Design an algorithm to determine which gas stations to stop to minimize the total number of stops. Give pseudocode. Prove that your algorithm returns an optimal solution and discuss running time of your algorithm. G8 G4 ++ G1 G2 G3 G5 G6 G7 G10 Figure 1: An example scenario. 4. (2% points) You are driving on a straight road from point s to point t in a car that can run for D miles on a full tank. There are n gas stations on the road and their locations with respect to the starting location s are given to you. You want minimize the number of stops that you need to make (for filling gas) for reaching from s to t. Assume that you have a full tank at start s. Design an algorithm to determine which gas stations to stop to minimize the total number of stops. Give pseudocode. Prove that your algorithm returns an optimal solution and discuss running time of your algorithm. G8 G4 ++ G1 G2 G3 G5 G6 G7 G10 Figure 1: An example scenario