Analysis Of Algorithms Let A and B be two sets of n positive integers. You get t

Question

Analysis Of Algorithms

Let A and B be two sets of n positive integers. You get to reorder each set however you like. After recording, let a_i be the i-th element of A and b_i be the i-th element of B. The goal is to maximize the function Product^n _i=1 a^b_i _i. You will develop a greedy algorithm for this task. (a) Describe a greedy idea on how to solve this problem, and shortly argue why you think it is correct (not a formal proof). (b) Describe your greedy algorithm in pseudocode. What is its runtime?

Explanation / Answer

Let set A be sorted so that a1a2a3…an and set B be sorted so that b1b2b3…bn. Pair ai with bi. This is the required solution.

.

Proof:
Suppose the optimal payoff is not produced from the above solution. Let S be the optimal solution, in which a1 is paired with bp and aq is paired with b1. Note that a1>aq and b1>bp.

Consider another solution S in which a1 is paired with b1, aq is paired with bp, and all other pairs are the same as S. Then
Payoff(S)/Payoff(S)=Sabii/Sabii=(a1)bp(aq)b1/(a1)b1(aq)bp=(a1/aq)bpb1
Since a1>aq and b1>bp, then Payoff(S)/Payoff(S)<1. This contradicts the assumption that S is the optimal solution.
Therefore a1 should be paired with b1.
Repeating the argument for remaining elements, we can get the result.

If the 2 sets A and B are already sorted, the time complexity is O(n).
If the sets are not sorted, then sort them first and the time complexity is O(nlogn)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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