1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
monitta
3 years ago
14

uppose you are going on a road trip with friends. Unfortunately, your headlights are broken, so you can only drive in the daytim

e. Therefore, on any given day you can drive no more than d miles. You have a map with n different hotels and the distances from your start point to each hotel x 1 < x 2 < ... < x n . Your final destination is the last hotel. Describe an efficient greedy algorithm that determines which hotels you should stay in if you want to minimize the number of days it takes you to get to your destination. What is the running time of your algorithm
Computers and Technology
1 answer:
tiny-mole [99]3 years ago
6 0

Answer:

Explanation:

Algorithm:

a. In each day, you will have to loop through the hotels that come to the hotel after you stayed last night.

b. If a hotel 'h' is found at more than 'd' distance away from last stayed hotel, then the hotel previous of 'h' is chosen to wait for that night. This is the greedy step, and you stay in this hotel.

c. The process for steps a and b is then repeated until we've reached the last hotel xn.

Running time:

Notice that the worst case occurs if each hotel is at a distance of successive multiples of 'd'. The best move is to estimate the distance to each hotel twice the whole computation in the scenario.

Thus, the total running time that could occur in the worst case is O(2n) = O(n). This is said to be linear time.

You might be interested in
Write three tasks students can preform in a digital classroom?
Nadya [2.5K]

Students can perform several tasks in a digital environment. For example, they can watch instructional videos, take notes, and participate in peer discussions.

this is the right answer .just did it

7 0
3 years ago
Read 2 more answers
The area where a blast originates is referred to what perimeter/isolation zone
Anna [14]
The area where a blast originate from is referred to as PERIMETER. After a bomb blast incident, the first responders has to map out a safe pre-blast perimeter based on the requirements of Bureau of Alcohol, Tobacco, Firearms and Explosives [BATFE]. After this, the first inner perimeter, also called hot zone must be established. This is where the blast originated from and it is the point where victims rescue and treatment will start.
8 0
3 years ago
What are some cowboy ethics??
lys-0071 [83]

Answer:

giv meh a min plsssss

Explanation:

4 0
3 years ago
What is the main advantage of using e-mail to complain about a service or product?
Dahasolnce [82]
The advantage of using email to complain about a service or product is that you are likely to get a faster response because this is the most common way in which complaints are tackled, and it also means you have a written record of the conversation between yourself and the company.
8 0
3 years ago
One group of students did an experiment to study the movement of ocean water. The steps of the experiment are listed below.
dsp73

The lamp and the ice bag were at the same place.  
Sounds like the experiment was intended to show on a small scale ocean currents from the poles to the equator and back to the poles. The bag of ice would simulate the cold at the poles while the lamp would simulate the heat provided by the sun near the equator. With that in mind, let's look at the possible flaws and see what is likely.  
Not enough ink was added.
 * If you can see the ink, then there's enough ink. So this isn't the correct choice.  
Not enough water was taken.
 * Possibility there wasn't enough volume of water to setup a current, but not too likely since the baking dish was filled. So let's look further. 
 The dish was too small for the experiment.
 * Same as above. It might be this, but there's something more likely. 
 The lamp and the ice bag were at the same place.
 * This sounds like a winner. In the real world, the poles are cold and the equator gets more sunlight. So there's a temperature gradient. In the described setup, both the heat sink (the bag of ice) and the heat source (the lamp) were at the same location.
5 0
3 years ago
Other questions:
  • What are the advantages of renting a home over buying a home? What are some disadvantages?
    13·1 answer
  • What role do mobile devices play in shaping the world?
    5·2 answers
  • A collection of methods that can be used by any class, as long as the class provides a definition to override the collection's a
    5·1 answer
  • In Labrador retrievers, black coats are dominant and brown coats are recessive. What is the genotype of a brown Labrador?
    5·1 answer
  • Como funciona la televisión
    7·1 answer
  • The alveolar walls and the pulmonary capillaries form the:
    5·1 answer
  • Line charts are best used for
    15·2 answers
  • Write a function called changeCharacter that takes three parameters – a character array, its size, and the replacement character
    15·1 answer
  • What is an algorithm?
    11·1 answer
  • What are two best practices for creating ads? (Choose two.) Select All Correct Responses Implement one ad per ad group per keywo
    12·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!