Question:
SubSet Sum using Greedy & Dynamic Algorithms
1. SubsetSum (greedy algorithms)
A SubsetSum is defined as follows: given positive integers a1 . . . an (not necessarily distinct), and a positive integer t, find a subset S of (1 . . . n) such that ∑iε s ai = t, if it exists.
a) Suppose each ai is at least twice as large as the sum of all smaller numbers aj . Give a greedy algorithm to solve SubsetSum under this assumption.
b) Prove correctness of your greedy algorithm by stating and proving the loop invariant.
2) SubsetSum (dynamic programming) Now suppose that the ai values are arbitrary. Design a dynamic programming algorithm to solve the SubsetSum problem. The running time of your algorithm should be polynomial in both n and t.
a) Give the definition of the array A you will use to solve this problem and state how you find out if there is such a set S from that array.
b) Give the recurrence to compute the elements of the array A, including initialization.
c) State how you would recover the actual set S given A .
d) Analyze the running time of your algorithm (including the step reconstructing S), in terms of n and t. hide problem.