Question

Professor Gekko has always dreamed of inline skating across North Dakota. He plans to cross the state on highway U.S. 2, which runs from Grand Forks, on the eastern border with Minnesota, to Williston, near the western border with Montana. The professor can carry two liters of water, and he can skate m miles before running out of water. (Because North Dakota is relatively flat, the professor does not have to worry about drinking water at a greater rate on uphill sections than on flat or downhill sections.) The professor will start in Grand Forks with two full liters of water. His official North Dakota state map shows all the places along U.S. 2 at which he can refill his water and the distances between these locations. The professor’s goal is to minimize the number of water stops along his route across the state.
a. Give an efficient algorithm by which he can determine which water stops he should make.

b. Prove that your strategy yields an optimal solution, and give its

Answer 1

The efficient algorithm by which he can determine which water stops he should make; has been determined below and the strategy which is the greedy strategy has been proven to yield an optimal solution.

To solve this question optimally, we will make use of the greedy solution.

In this method, we will maximize the distance that can be covered from a particular point in such a way that there must be a place where water can be gotten before a run out is experienced.

Now, the first point at which there will be a stop should be located at a point that is farthest from the starting position and is also made to be ≤ m miles from the starting position.

Now, this this situation is one that shows optimal substructure and since our  first stopping point will be made to be at p, it means that we are solving the sub-question with the assumption that our starting point is at p.

When we combine the two stated plans above, we will arrive at an optimal solution for the normal reasons via cut and paste.

B) Now we need to show that the greedy approach earlier used produce a first stopping point which is contained in the optimal solution.

Let O represent any optimal solution whereby the professor stops at positions o₁, o₂, o₃....oₙ.

Let h₁ represent the farthest stopping point that is reachable from the starting point. Then we can replace o₁ by h₂ to generate a modified solution H since o₁ - o₂ < o₂ - h₁.

Finally, we can really make it to the positions in H without having to run out of water and since H has the same number of stops, we can conclude that h₁   is contained in one of optimal solution.

Therefore our strategy which is the greedy strategy has been proven to work.

Read more about algorithms at; brainly.com/question/24793921