# 1 Suppose you’ve been sent back in time and have arrived at the sce

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, the n 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.
Solution
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.
Name:
Description:

Calculate the price
Pages (550 words)
\$0.00
*Price with a welcome 15% discount applied.
Pro tip: If you want to save more money and pay the lowest price, you need to set a more extended deadline.
We know how difficult it is to be a student these days. That's why our prices are one of the most affordable on the market, and there are no hidden fees.

Instead, we offer bonuses, discounts, and free services to make your experience outstanding.
How it works
Receive a 100% original paper that will pass Turnitin from a top essay writing service
step 1
Fill out the order form and provide paper details. You can even attach screenshots or add additional instructions later. If something is not clear or missing, the writer will contact you for clarification.
Pro service tips
One writer throughout the entire course
If you like the writer, you can hire them again. Just copy & paste their ID on the order form ("Preferred Writer's ID" field). This way, your vocabulary will be uniform, and the writer will be aware of your needs.
The same paper from different writers
You can order essay or any other work from two different writers to choose the best one or give another version to a friend. This can be done through the add-on "Same paper from another writer."
Copy of sources used by the writer
Our college essay writers work with ScienceDirect and other databases. They can send you articles or materials used in PDF or through screenshots. Just tick the "Copy of sources" field on the order form.
Testimonials
See why 20k+ students have chosen us as their sole writing assistance provider
Check out the latest reviews and opinions submitted by real customers worldwide and make an informed decision.
11,595
Customer reviews in total
96%
Current satisfaction rate
3 pages
Average paper length
37%
Customers referred by a friend