Question 8 in HW5

Question 8 in HW5

student (guest) 03 Jul 2015 01:54

can you please explain why in the solution we choose the max{A[i],A[n-2i]}

Re: Question 8 in HW5

Shai V 04 Jul 2015 09:07

You choose 2 subsets of size i and weigh them against each other… if one is heavier, you know the heaviest coin is in that one (of size i), so you need to spend A[i] to find the heaviest. If neither group is heavier, the heaviest coin must be in what is left, which is of size n-2i.

נועה (guest) 04 Jul 2015 13:09

אז למעשה המקסימום מתייחס למקרה הגרוע לפי מה שאני מבינה מההסבר שלך?

Shai V 04 Jul 2015 15:15

yes, we can only count on the worst case…
if we can count on the best case happening, let's just weight 1 coin against 1 coin. In the best case, one will be heavier and we are done.
A lot of these dynamic programming questions ask something on the lines of "what is the best thing you can GUARANTEE", no matter what happens in the weighing/throwing/stacking etc.