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

Question

08-12-2021
Computers and Technology

contestada

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

Respuesta :

Otras preguntas

Describe the conflicting viewpoints between China and Tibet wit regard to Tibet's autonomy. where does Tibet stand today wit regard to Chinese rule?

Monomers are small, individual molecules that are used to build larger molecules. Polymers are large organic molecules that are built from monomers. What type o

The United Farm Workers has affected American society by: A. seeking civil rights for Latinos. O B. ending modern sharecropping. C. destroying fully automated f

WILL GIVE BRAINLIST TO BEST ASNWER GOOD EASY POINTS! Quick Write for my ela class My Weekend In 5 sentences, tell me about the highs and lows of your weekend.

Which best represents the addition of the two gray parts and the striped part in the whole rectangle?

PLEASE HELP I WILL MARK BRAINLIEST!!!!!! In the 1920s, a movement of artists and writers in Europe rejected traditional forms of writing (Modernists!). What did

PLEASE HELPLee realizes he has much more work than anyone else in the group, and he's forced to stay up late to finish his portion. Which question did the group

'Write a letter to your District chief executive telling him the three things you need in your school

What did the chicano movement accomplished? in detail

Which event most likely represents Atalanta's transformation? O slaying the boar O being raised by hunters O losing the race to Meilanion O collecting the golde

AFOKE88 AFOKE88 · Answer 1 · 2021-12-21T14:36:14+01:00

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; https://brainly.com/question/24793921