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
What is a bitmap ???
leva [86]
<span>a representation in which each item corresponds to one or more bits of information, especially the information used to control the display of a computer screen.
</span><span>represent (an item) as a bitmap.
</span>
4 0
3 years ago
Read 2 more answers
This process can be applied to help workers choose the best telecommunications technology to do a specific task.
Lisa [10]
B. Internet Telephony would be my best guess. I'm not that good with computers. Hope this Helps :-)
4 0
3 years ago
Read 2 more answers
What is the difference between the default constructor and the overloaded constructor?
lukranit [14]

Explanation:

A default constructor is a constructor that present in the class by default with no parameters when we write a new constructor with parameters it is called overloaded constructor.There can be different overloaded constructors in the same class.

The main difference between default constructor and overloaded constructor is that the default constructor does't have any parameters while the overloaded constructors have parameters.

4 0
3 years ago
Technician A says that the excessive length of a heater hose is intended to protect the heater core from undue stress. Technicia
hammer [34]
It is both true that <span>Technician A says that the excessive length of a heater hose is intended to protect the heater core from undue stress. Technician B says that excessive wear adds to the length of a heater hose, and a replacement heater hose should be roughly three to four inches shorter than its predecessor.  So the asnwer is letter B.</span>
6 0
3 years ago
How do I convert years to days on Python. For example, if I were to enter 3 years it should output "You are 1095 days old".
Scorpion4ik [409]

years = int(input("Enter the # of years: "))

print("You are "+str(years*365)+" days old")

I wrote the code in python 3.8. I hope this helps!

6 0
3 years ago
Other questions:
  • Problem 2 (40 points)-Write a program. Submit a file named weight.cpp Create a program that continuously allows a user to enter
    5·1 answer
  • You listened to a song on your computer. Did you use hardware or software? Explain.
    11·2 answers
  • .Although SQL is a language, you don’t use it to write applications? (true, false)
    8·1 answer
  • A type of indent where the first line of text starts at the left margin and the second and succeeding lines of text are indented
    7·2 answers
  • What is the least number of bits you would need to borrow from the network portion of a Class B subnet mask to get at least 130
    10·1 answer
  • Choose the term that matches each description.
    15·1 answer
  • First calculating device​
    12·2 answers
  • A buffer storage that improve computer performance by reducing access time is​
    13·1 answer
  • The advancement of technology in our daily lives has changed how we interact with the world.
    10·1 answer
  • 1.
    7·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!