ECS 122A: Final “Exam” Instructor: Aaron Kaloti Winter 2020 1 Changelist • v.1: Initial version. • v.2: Need to say where the optimal solution is in part (c) of the DP problem. 2 Regarding Submission • You will be penalized if, when submitting on Gradescope, you mark the wrong page for a given homework problem. • Your submission must be typed up using Latex. I recommend using Overleaf, a website which allows collaboration on Latex documents. 3 Regarding Collaboration • You may not copy answers from online sources such as Chegg, StackOverflow, or any solutions manual of any of the textbooks (primary or otherwise) used in this class. • When you submit on Gradescope, it will let you choose your group. Click here for what I assume this is supposed to look like (although I don’t know why there are more dislikes than likes). If you have issues with this, feel free to email me. • Your group size cannot be more than five. • List the members of your group below. 1 4 Problems 1. Do all three parts of problem #4 on page 315 of our primary textbook. (This is problem #4 among the exercises for Chapter 6, and it starts with the words “Suppose you’re running a lightweight consulting business…”.) For part (c), you need only provide the recurrences (you need two recurrences for this problem) and what the optimal solution would be for n months in terms of your two recurrences. (To clarify what I mean: normally, if there were one recurrence, we would typically say that OPT (n) is the optimal solution for n, where n is whatever. However, this doesn’t work here, since there are two recurrences needed.) Part (a): Part (b): Part (c): 2. The Subset Sum Problem is as follows: Given a set S of positive integers and an integer target t > 0, does there exist a subset S′ ⊆ S whose elements sum to t? For example, if S = {3, 8, 15, 29} and t = 23, then the answer is “yes”, as shown by S′ = {8, 15}. The Set Partition Problem is as follows: Given a set S of numbers, can the numbers be partitioned into two sets A and A¯ = S − A such that ∑ x∈A x = ∑ x∈A¯ x. For example, if S = {2, 3, 5, 6}, then the answer is “yes”, as shown by A = {2, 6} and A¯ = S −A = {3, 5}. Given that the Subset Sum Problem is NP-hard, show that the Set Partition Problem is NP-hard by showing that Subset Sum Problem ≤P Set Partition Problem. Hint : Since you are showing that Subset Sum Problem ≤P Set Partition Problem, you have a “black box” that solves arbitrary instances of the Set Partition Problem. (This may seem odd, given that we are trying to prove the hardness 2 of the Set Partition Problem.) Thus, for any instance of the Subset Sum Problem, you need to figure out how to twist the input into an input to the Set Partition Problem, such that the “black box” answers yes if and only if the answer to the original Subset Sum Problem instance was “yes”. Recall that when we reduced the 3-SAT Problem to the Independent Set Problem, we had to figure out how to translate an arbitrary instance of the 3-SAT Problem (i.e. k clauses over n terms) to an instance of the Independent Set Problem (i.e. a graph G and an integer k). There is a similar consideration here: part of what you must do is figure out how to translate an arbitrary instance of the Subset Sum Problem (i.e. a set S of positive integers and an integer target t > 0) to an instance of the Set Partition Problem (i.e. a set S of numbers). Do notice that t is not part of the input to the Set Partition Problem. 3
