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
Name the hardware component that performs each of the following functions (1) performs calculation and/or comparisons (2) holds
mariarad [96]
1. The CPU (central processing unit) does the calculations and comparisons that make the computer work. They use millions of transistors to do so.
2. The ROM holds all the programs on the computer. This is most often the "C" drive.
3. The ROM also has the operating system that is used to run the computer.
6 0
3 years ago
WILL UPVOTE NEED ANSWERS ASAP i have till 4:30
deff fn [24]
B. Summer monsoons bring heavy rainfall and winter monsoons create dry and arid conditions.
6 0
3 years ago
What is the purpose of the Occupational Safety and Health Act?
NikAS [45]

Answer:

The purpose of this act was to reduce workplace hazards and implement more safety and health programs for both employers and their employees.  

3 0
3 years ago
Read 2 more answers
Assume that the classes listed in the Java Quick Reference have been imported where appropriate.
Taya2010 [7]

Answer:

Attached is a screenshot of my code for 'PasswordGenerator' and the tests necessary.

Explanation:

If you need any explanation, please ask!

3 0
2 years ago
Read 2 more answers
Swapping two numbers
Tju [1.3M]

Answer:

Swapping two numbers means exchange the values of two variables with each other.

8 0
3 years ago
Other questions:
  • What is the difference between a learner’s license and an operator’s license?
    13·1 answer
  • 52.
    11·1 answer
  • After saving her presentation initially, Leah realizes she needs to add another content slide. She adds the slide and is ready t
    7·1 answer
  • Select the correct answer.
    10·2 answers
  • How to simplify???? 2(-3x^2+6x+1)-2(4x^2-3x+1)<br><br>​
    7·1 answer
  • L00000000000000000000000000000000000000000000000000000000l they b00ty tickled
    6·2 answers
  • How is a UDP socket fully identified? What about a TCP socket? What is the difference between the full identification of both so
    9·1 answer
  • What is the most common type of storage device for transferring files from one computer to another?
    10·1 answer
  • Exam Instructions
    6·1 answer
  • the php function that is executed is a connection to a database cannot be made is the____ function. die | isset| end | connect.
    8·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!