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
Program:
Mkey [24]

Answer:

See explaination

Explanation:

#method to print menu & handle user choice

def print_menu(input_str):

#printing menu

print('MENU')

print('c - Number of non-whitespace characters')

print('w - Number of words')

print('f - Fix capitalization')

print('r - Replace punctuation')

print('s - Shorten spaces')

print('q - Quit\n')

#getting choice

choice=input('Choose an option: ').lower()

#identifying choice

if choice=='c':

#displaying number of non white space chars in input_str

print('Number of non-whitespace characters:',get_num_of_non_WS_characters(input_str))

elif choice=='w':

#displaying number of words in input_str

print('Number of words:',get_num_of_words(input_str))

elif choice=='f':

#fixing capitalization and getting updated string and count of values capitalized

input_str,count=fix_capilization(input_str)

#displaying results

print('Number of letters capitalized:',count)

print('Edited text:',input_str)

elif choice=='r':

#replacing punctuation, displaying updated text

input_str=replace_punctuation(input_str)

print('Edited text:', input_str)

elif choice=='s':

#shortening spaces and displaying updated text

input_str = shorten_space(input_str)

print('Edited text:', input_str)

#returning choice and input_str

return choice,input_str

#returns the number of non white space chars in input_str

def get_num_of_non_WS_characters(input_str):

count=0

#looping through each character in input_str

for i in input_str:

if not i.isspace():

#i is not a space

count+=1

return count

#returns the number of words in input_str

def get_num_of_words(input_str):

#splitting words into list of tokens by space

words=input_str.split(' ')

count=0

#counting all non empty strings in words list

for i in words:

if len(i)>0:

count+=1

return count

#method to fix capitalization and return updated string and count of letters updated

def fix_capilization(input_str):

count=0

beginning=True #starting letter should be capitalized

result=''

for i in input_str:

if beginning and i.isalpha():

#start of a sentence and i is alphabetic

if i.islower():

#converting i to upper case, incrementing count

i=i.upper()

count+=1

result+=i

#not start of a sentence

beginning=False

elif i in '?.!':

#i is either ? or . or !, next letter should be capitalized

beginning=True

result+=i

else:

#any other character

result+=i

return result,count

#method to replace exclamation and semicolons with period and comma respectively

def replace_punctuation(input_str,exclamationCount =0,semicolonCount=0):

result=''

for i in input_str:

if i=='!':

i='.'

exclamationCount+=1

elif i==';':

i=','

semicolonCount+=1

result+=i

print('Punctuation replaced')

#displaying replaced values counts

print('exclamationCount:',exclamationCount)

print('semicolonCount:',semicolonCount)

return result

#removes all double or more spaces in input_str

def shorten_space(input_str):

input_str=input_str.strip()

result=''

prev=None

for i in input_str:

if prev==None:

result+=i

elif i==' ':

if prev != ' ':

result+=i

else:

result+=i

prev=i

return result

if __name__ == '__main__':

#getting input, printing it

input_str=input('Enter a sample text:\n')

print('\nYou entered:',input_str)

choice=' '

#looping until choice becomes q

while choice!='q':

choice,input_str=print_menu(input_str)

7 0
3 years ago
Which of these words does not describe factual data
kipiarov [429]
The correct answer is "opinion".

<span>Opinions are almost never factual which is why they are opinions. </span>
5 0
3 years ago
Read 2 more answers
Need the answer ASAP!!! I’ll mark brainliest if correct
san4es73 [151]

Answer:

update standerds

Explanation:

7 0
3 years ago
Write a Java program to accept an item's name and price from the user and output them to the console
Anit [1.1K]

Answer:

// program in java.

// package

import java.util.*;

// class definition

class Main

{// main method of the class

public static void main (String[] args) throws java.lang.Exception

{

   try{

    // scanner object to read inputs

Scanner scr=new Scanner(System.in);

 // variables

String name;

   double price;

   System.out.print("Enter item's name: ");

   // read item's name

   name = scr.next();

   System.out.print("Enter item's price: ");

   // read item's price

   price= scr.nextDouble();

   // print name

   System.out.println("name of item is:"+name);

   // print price

   System.out.println("price of item is:"+price);

   }catch(Exception ex){

       return;}

}

}

Explanation:

Read name & price of item from user and assign it to variables "name" & "price" respectively with scanner object.Then print the name and price of item .

Output:

Enter item's name: Apple                                                                                                  

Enter item's price: 100                                                                                                    

name of item is:Apple                                                                                                      

price of item is:100.0

6 0
3 years ago
Which of the following is a job description for a person with a degree in Information Technology? radiology engineer web develop
Jet001 [13]

Answer: Web developer

Explanation: Web developer is a job where you have to develop World Wide Web applications by programming or applications that run over the internet, and this degree would need a degree in information technology

The other degrees needed for the following jobs:

1.    Radiology engineer: Radiology is a study of diagnosing and treating diseases with the help of medical imaging. So, it needs a degree in medical combined with physics and chemistry.

2.    Toxicologist broadcast technician: is a job where the technician has to determine the factors which contributed to a person’s death. So, a person should have a degree in medicine to become a toxicologist technician

6 0
3 years ago
Other questions:
  • Create a program to deteate a program to determine whether a user-specified altitude [meters] is in the troposphere, lower strat
    11·1 answer
  • Why is it important to save a print copy of electronic sources
    5·1 answer
  • Which line of code will print I can code on the screen?
    13·1 answer
  • 1.Terry turned on his computer one day to find that all of the storage on his computer was filled up. Furthermore, there were ma
    6·1 answer
  • 2. An evil twin attack that broadcasts a legitimate SSID for an unauthorized network is an example of what category of threat? A
    9·1 answer
  • The repeated use of electronic communications, such as chat rooms and email, to seek out, harass, or frighten someone is called
    12·1 answer
  • Computers help eliminate that repetitive of manual task. How can this benefit you in in your overall career
    7·2 answers
  • The rock cycle _____.
    14·1 answer
  • Which types of file formats are the best choice for files that may need to be edited later?
    14·1 answer
  • How can you make a search phrase more effective?
    11·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!