My colleague, Dr. Strange tells me that there is an alternate universe where Sydney buses are never cancelled and they always run on time; in fact, bus timetables specify to the second the exact arrival and departure time of each bus on each stop. Sadly, in this alternate reality there are no free transfers (i.e., you need to pay for the full fare of every bus you ride) and different bus lines charge different fees (but the good news is that the fee is flat and does not depend on distance travelled). A travel plan is a sequence of stop-time pairs where stop is a location of a bus stop and time is when we arrive at that stop. The plan is feasible if for any two consecutive pairs (a, t) and (b, t′) in the plan there exists a bus that departs after t and arrives at b at exactly t′. That is, a travel plan does not allow us to walk between stops. Assuming that no two buses arrive at the same time at the same stop, a feasible plan uniquely identifies the bus lines that we need to take to realize the plan. The cost of the plan is the sum of the fares we need to pay. Your task is to design an efficient algorithm that given a departure time t, an arrival time t′, an origin stop a and a destination stop b, finds the cheapest travel plan from a to b that obeys the departure and arrival time constraints (we start travelling at or after t and we arrive to our destination at or before t′). Remember to: a) Describe your algorithm in plain English. b) Prove the correctness of your algorithm. c) Analyze the time complexity of your algorithm. Suppose that in this alternative universe, there are m bus lines, each having k instances, and each having exactly ℓ stops. The timetable is therefore made up of mk lists (one for each instance of each bus line) each having triplets of the form (stop, arrival, departure), so the size of the instance is Θ(mkℓ). The algorithm must run in time that is polynomial on m, k, and ℓ.
My colleague, Dr. Strange tells me that there is an alternate universe where Sydney buses are never cancelled and they always run on time; in fact, bus timetables specify to the second the exact arrival and departure time of each bus on each stop. Sadly, in this alternate reality there are no free transfers (i.e., you need to pay for the full fare of every bus you ride) and different bus lines charge different fees (but the good news is that the fee is flat and does not depend on distance travelled).
A travel plan is a sequence of stop-time pairs where stop is a location of a bus stop and time is when we arrive at that stop. The plan is feasible if for any two consecutive pairs (a, t) and (b, t′) in the plan there exists a bus that departs after t and arrives at b at exactly t′. That is, a travel plan does not allow us to walk between stops. Assuming that no two buses arrive at the same time at the same stop, a feasible plan uniquely identifies the bus lines that we need to take to realize the plan. The cost of the plan is the sum of the fares we need to pay. Your task is to design an efficient algorithm that given a departure time t, an arrival time t′, an origin stop a and a destination stop b, finds the cheapest travel plan from a to b that obeys the departure and arrival time constraints (we start travelling at or after t and we arrive to our destination at or before t′).
Remember to:
a) Describe your algorithm in plain English.
b) Prove the correctness of your algorithm.
c) Analyze the time complexity of your algorithm.
Suppose that in this alternative universe, there are m bus lines, each having k instances, and each having exactly ℓ stops. The timetable is therefore made up of mk lists (one for each instance of each bus line) each having triplets of the form (stop, arrival, departure), so the size of the instance is Θ(mkℓ). The algorithm must run in time that is polynomial on m, k, and ℓ.
Step by step
Solved in 3 steps
