More reductions given an array a = [a1, a2, . . , an] of nonnegative integers, consider the following problems: 1 p partition: determine whether there is a subset p ⊆ [n] ([n] : = {1, 2, · · · , n}) such that i∈p ai = p j∈[n]\p aj 2 subset sum: given some integer k, determine whether there is a subset p ⊆ [n] such that p i∈p ai = k 3 knapsack: given some set of items each with weight wi and value vi , and fixed numbers w and v , determine whether there is some subset p ⊆ [n] such that p p i∈p wi ≤ w and i∈p vi ≥ v for each of the following clearly describe your reduction, justify runtime and correctness.
(a) find a linear time reduction from subset sum to partition.
(b) find a linear time reduction from subset sum to knapsack