Consider the Partition problem: we are given a set I of n positive integers and want to decide if there is a partition o

[correctanswer]

Consider The Partition Problem We Are Given A Set I Of N Positive Integers And Want To Decide If There Is A Partition O 1 (541.81 KiB) Viewed 115 times

Consider the Partition problem: we are given a set I of n positive integers and want to decide if there is a partition of I into two sets I₁ and I₂ such that the sum of I₁ is equal to the sum of I2. Consider the following greedy algorithm: initialize I₁ and 1₂ to be empty; iterate through I in ascending order and place the current integer in whichever of 1₁ and 1₂ is lower. We break ties in favor of I₁. If at the end, the sum of I₁ equals the sum of I2, we return "Yes" otherwise we return "No". In the following, we use w; to denote the i-th smallest integer, i.e. w₁ ≤ w₂ ≤...≤ Wn. Algorithm 1 Greedy 1: function GREEDY (1) I₁0 and I₂ + 0 2: 3: for i 1; i <n; i++ do 4: if sum of I₁ is at most sum of I₂ then 5: I₁I₁U {w₁} 6: end if 7: end for 8: if sum of I₁ is equal to sum of I₂ then 9: return Yes 10: else 11: return No 12: end if 13: end function Your task is to show that there exists a set I of positive integers such that there is a partition of I into sets J₁ and J2 such that the sum of J₁ is equal to the sum of J₂ but the greedy algorithm returns No. (a) Describe the set I. (b) Describe the sets I₁ and I2 at the end of the greedy algorithm. (c) Describe a partition of I into two equal-sum sets J₁ and J₂.