Please type your solution very clearly
- Theory Of Computation Please Type Your Solution Very Clearly 1 (73.46 KiB) Viewed 75 times
Theory of Computation. Please type your solution very clearly
-
answerhappygod
- Site Admin
- Posts: 899603
- Joined: Mon Aug 02, 2021 8:13 am
Theory of Computation. Please type your solution very clearly
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.)
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.)