For this programming assignment, you will implement a number of heuristics for solving the Number Partition problem, which is (of course) NP-complete. As input, the number partition problem takes a sequence A = (a1, a2, . . . , an) of non-negative integers. The output is a sequence S = (s1, s2, . . . , sn) of signs si {1, 1} such that the residue u = nX i=1 siai is minimized. Another way to view the problem is the goal is to split the set (or multi-set) of numbers given by A into two subsets A1 and A2 with roughly equal sums. The absolute value of the difference of the sums is the residue. As a warm-up exercise, you will first prove that even though Number Partition is NP-complete, it can be solved in pseudo-polynomial time. That is, suppose the sequence of terms in A sum up to some number b. Then each of the numbers in A has at most log b bits, so a polynomial time algorithm would take time polynomial in n log b. Instead you should find a dynamic programming algorithm that takes time polynomial in nb. Give a dynamic programming solution to