Your friend is taking a trip from Anchorage (Alaska) to Rio de Janeiro (Brazil)
ID: 3748729 • Letter: Y
Question
Your friend is taking a trip from Anchorage (Alaska) to Rio de Janeiro (Brazil) by airplane. However, a direct flight between those two cities is not an option because your friend gets severely airsick and is restricted to flights of 30 minutes long. Your friend desires to minimize the total number of flights that are needed to complete the journey from Anchorage to Rio de Janeiro. While flight bookings can only be made when at the departing airport, you do already know the flight time each potential airport you could stop at is from Anchorage. For simplicity assume that you can arrange all the potential airports in a straight line from Anchorage to Rio de Janeiro, sorted by the total travel time from Anchorage. Ignore waiting time between flights. Create a greedy algorithm to solve this problem for your friend, letting the sorted travel times be 0 = t0 t1 . . . , tn where the subscript indicates a specific city, and city 0 and city n are Anchorage and Rio de Janeiro, respectively. Use all times to be in minutes, and tn = 30 hours. Use precise mathematical notation to express your answers.
(a) What does a solution to the problem look like? HINT: think set theory
(b) (2 points) What is a best case scenario? Explain.
(c) (4 points) What is a worst case scenario? Explain.
(d) (8 points) Find and prove a tight bound for the worst case runtime. Show all your work.
Explanation / Answer
Answer b)
The best case scenario will be :
if we consider each city in between Anchorage and Rio de Janerio, which has a duration of 30 min between them and then try to frame a solution, it should produce the best case scenario.
Since the distance between Anchorage and Rio de Janerio is 30 hours , the friend will require to take 60 flights at a minimum, since he cannot take a flight longer than 30 mins, so with two flights he will have to cover 1 hour therefore he will cover 30 hours with 60 flights.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.