Question :

Please do not write an answer form the internet,You want very clear algorithm with mathematical prove of correction if that can be possible.

You are going on a trip from Halifax to San Francisco. You know that, along the route, there are gas stations at kilometers k 1, k 2, . . . , k n.

You also know that your car can go m kilometers on a tank full of gas. Develop an algorithm that determines at which gas stations to stop so that

a. The distance between two consecutive stops is at most m (that is, you can always get from one stop to the next on a tank full of gas) and

b. You make as few stops as possible while respecting the previous condition. The running time of your algorithm should be linear. You do not have to prove that it is.

Prove that your algorithm is correct, that is, that it indeed produces a sequence of stops that satisfies the above conditions.