Suppose you want to fly from Des Moines to San Diego. You would like to find a l

Question

Suppose you want to fly from Des Moines to San Diego. You would like to find a less expensive flight with a short travel time. When you search on a travel web site, you will be given a lot of itineraries. We will view each itinerary as a tuple (cost, time). Suppose A1 (c1, t1 and A2 (c2, t2) are two itineraries. We say that A1 dominates A2, if c1 c2 and t2 (both the cost and travel time with itinerary A1 are better compared to A2). Given a set of of itineraries A1, A2, An, we say that an itinerary Ai is undesirable if there exists an itinerary Ai (i j) such that Aj dominates Ai. An itinerary Ai is desirable if it is not undesirable. Given a list of itineraries, your first task would be to eliminate all undesirable itineraries (and decide on one of the desirable itineraries). Give an algorithm that gets a set S consisting off n itineraries as input and outputs all desirable itineraries from S. Your grade depends on the run time of your algorithm.

Explanation / Answer

Consider an array of itineraries A[i…..r]

Step 1: Divide the array by finding the middle element of the array by adding i and r and divide by two.

Step 2: Conquer the problem by finding the best itinerary using c1<c2 and t1<t2 condition recursively on the sub-arrays in each of the two sub-problems created by divide step

Step 3: Combine the result by comparing itineraries of both sub-problems using c1<c2 and t1<t2 condition

Recurrence relation for algorithm: T(n) = 2 T(n/2) + O(n)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.