In this programming question, we will be considering the NUMBER PARTITION problem.

As input, the number partition problem takes a sequence A = (a1, a2, . . . an) of non-negative integers, and outputs a sequence S = (s1, s2, . . . sn) of signs s_i {1, +1} such that the residue

u=i=1nsiai

is minimized. Another way to view the problem is to split the set (or multi-set) of numbers given by A into two subsets A1 and A2 whose sums are as equal as possible. The absolute value of the difference of the sums is the residue.

(a.) NUMBER PARTITION can be solved exactly in time polynomial in n and B. Find and implement a dynamic programming algorithm that has worst-case running time that is a polynomial function of n and B. As always, justify correctness, formulate a DP recurrence and analyze the running time.