1. Suppose you’ve been sent back in time and have arrived at the scene of an anc

Question

1. Suppose you’ve been sent back in time and have arrived at the scene of an ancient Roman battle. Moreover, suppose you have just learned that it is your job to assign n spears to n Roman soldiers, so that each man has a spear. You observe that the men and spears are of various heights, and you have been told (in Latin) that the army is at its best if you can minimize the total difference in heights between each man and his spear. That is, if the ith man has height mi and his spear has height si, then you want to minimize the sum, i=1 to n |mi si|. Consider a greedy strategy of repeatedly matching the man and spear that minimizes the difference in heights between these two. Prove or disprove that this greedy strategy results in the optimal assignment of spears to men.

2. Consider again the time-travel problem of the previous exercise,but now consider a greedy algorithm that sorts the men by increasing heights and sorts the spears by increasing heights, and then assigns the ith spear in the ordered list of spears to the ith man in the ordered list of Roman soldiers. Prove or disprove that this greedy strategy results in the optimal assignment of spears to men.

Explanation / Answer

1. Given: Army- N men and N spears are of various heighThe Army is at its best if you can minimize the total difference in heights between each man and his spear. That is, if the ith man has height mi and his spear has height si, then you want to minimize the sum, i=1 to n |mi si|

Greedy Approach says always select the local optimum value.Greedy Approach will do the optimal assignment of spears to men.

Proof: - let we given n spear of height s1,s2,------, sn and n army men of height a1,a2-----an.

using greedy approach, we will select army men of minimum height and corresponding spear of minimum height. so the difference between ai-si will be minimum.

Now we left with n-1 spear and person. Again and again, we will select spear and army men of miminum height from remaining local poll untill all men are assigned a spear.So in this way overall differnece will be minimum and greedy will give optimal solution.

2.Given:-greedy algorithm that sorts the men by increasing heights and sorts the spears by increasing heights, and then assigns the ith spear in the ordered list of spears to the ith man in the ordered list of Roman soldiers.

Yes,this greedy strategy will also results in the optimal assignment of spears to men.

Proof:-Beacause greedy always follow local optimal approach. As all spear and men are sorted according to their heights. so assignment of ith spear to ith men is best one. and we get solution.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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