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