Problem 2 [10 marks] Consider the Partition problem: we are given a set I of n positive integers and want to decide if t

[correctanswer]

Problem 2 10 Marks Consider The Partition Problem We Are Given A Set I Of N Positive Integers And Want To Decide If T 1 (159.51 KiB) Viewed 51 times

Problem 2 [10 marks] 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 I₂. 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) 2: I₁0 and 1₂0 3: for i1; i<n; i++ do if sum of I₁ is at most sum of I₂ then 5: I+IU{w} 6: end if 7: end for 8: if sum of I₁ is equal to sum of 1₂ 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 J₂ 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 1₁ and 12 at the end of the greedy algorithm. (c) Describe a partition of I into two equal-sum sets J₁ and J₂.