This is all given by instructor

1. Partitioning and packing In the Partition problem, you are given a set {a1, a2, An} of nonnegative integers, and you are asked to decide whether there is a subset S C [1,2,...,n) such that EXiesa,-Xigs ai In the Bin Packing problem, you are given n items with sizes si (0,1], and you are asked to find an assignment of items to as few bins as possible so that the total size of all items in a bin is at most 1. (In other words, you are asked to choose a bin b, E 1,2,...,k) for each item ie [1,2,...,n] such that ibbsi S 1 for all bins b e 11,2,. . . ,k], with k minimal) (a) Show that Partition Sp Bin Packing (b) Using only the result of the previous part and your knowledge of P and NP: i. If someone tells you that Partition is NP-hard, what can you conclude about the ii. If someone tells you that Bin Packing is NP-hard, what can you conclude about the iii. If someone tells you that Partition has a polynomial-time algorithm, what can you iv. If someone tells you that Bin Packing has a polynomial-time algorithm, what can you hardness of Bin Packing? hardness of Partition? conclude about the hardness of Bin Packing? conclude about the hardness of Partition? 1. Partitioning and packing In the Partition problem, you are given a set {a1, a2, An} of nonnegative integers, and you are asked to decide whether there is a subset S C [1,2,...,n) such that EXiesa,-Xigs ai In the Bin Packing problem, you are given n items with sizes si (0,1], and you are asked to find an assignment of items to as few bins as possible so that the total size of all items in a bin is at most 1. (In other words, you are asked to choose a bin b, E 1,2,...,k) for each item ie [1,2,...,n] such that ibbsi S 1 for all bins b e 11,2,. . . ,k], with k minimal) (a) Show that Partition Sp Bin Packing (b) Using only the result of the previous part and your knowledge of P and NP: i. If someone tells you that Partition is NP-hard, what can you conclude about the ii. If someone tells you that Bin Packing is NP-hard, what can you conclude about the iii. If someone tells you that Partition has a polynomial-time algorithm, what can you iv. If someone tells you that Bin Packing has a polynomial-time algorithm, what can you hardness of Bin Packing? hardness of Partition? conclude about the hardness of Bin Packing? conclude about the hardness of Partition