Problem $2(10=10)$ Subset Sum

In the Subset Sum problem, we are given a set A $=\{$a$1,$ a$2,...,$ an$\}$ of n non$-$negative integers and another

non$-$negative integer b$,$ and are asked to determine if there exists a subset of A whose sum is exactly b$.$ So$,$

an algorithm for Subset Sum takes as input A and b and returns True if there exists a subset of A whose

sum is exactly b$,$ and False otherwise.

$($a$)$ Suppose you are given an algorithm to solve the Knapsack problem. Show how the Subset Sum problem

can be solved by building an instance of the Knapsack problem and then using the Knapsack algorithm.

$($b$)$ Here, we consider a more direct dynamic programming algorithm. Let SubsetSum$[$i$,$ s$]$ be True if

there is a subset of $\{$a$1,...,$ ai$\}$ whose sum is s$,$ and False otherwise. Note that the Subset Sum

problem is asking to find SubsetSum$[$n$,$ b$].$ Show that for any i $>1$ and s $>0,$ SubsetSum$[$i$,$ s$]$ can

be determined from the values of SubsetSum$[$i $1,].$ Using this, establish a recurrence relation for

SubsetSum$[$i$,$ s$].$ Remember to include base cases.

$($c$)$ Convert the recurrence of part $($b$)$ to a bottom$-$up dynamic programming algorithm. Analyze its

running time.