Answer Happy

Theory of Computation.
Please type your solution very clearly
(10 points) Consider the following language UNARY-MULTISET-SUM = ={10 B is unary (B, X1, . . . Xn)|There is a combination of x;'s (repeats allowed) that add up to B As an example: (31, 7, 4, 9) E UNARY-MULTISET-SUM because 31 = 9+7+7+4+4. Note how we can repeat numbers, unlike the subset sum problem we studied in class • (101,4,6,8) ¢ UNARY-MULTISET-SUM) because 101 is odd, but 4, 6, 8 are all even 1 Note that technically 31 and 101 would be represented in unary, i.e. lood and Il-. 31 101 Prove that UNARY-MULTISET-SUM EP. (Hint: Start by making a 1-D array A of size B+1. Use dynamic programming to fill in the array.)