Given a set S of integers, an integer total, and a non-negative integer budget, the SubsetSum Decision problem is to report whether or not there is a subset of S, containing at most budget elements, that sums to total. Given a set 5 of integers, an integer total, and a non-negative integer budget, the SubsetSumSearch problem is to find a subset of S, containing at most budget elements, that sums to total or to report that no such set exists. A) Suppose you have a polynomial time algorithm called SSD that solves the SubsetSum Decision problem. Describe, in clear and concise English, a polynomial time algorithm called SSS that solves the SubsetSumSearch problem. (Hint: SSS should call SSD multiple times.) You should not need more than five sentences or so. B) Suppose S is a set containing in integers, and that SSD/S, total, budget) is Off(n)). What of these is the tightest upper bound on the running time of SSS(S, total, budget)? a. O(n f(n)) b. O(f(n)^2) c. O(f(n) log n) d. O(f(n^2)) QUESTION 2 a) Define Primitive data type. b) List TWO (2) types of Recursive cases. c) State TWO (2) disadvantages of an array list. d) Give ONE (1) difference between Perfect binary tree and Full binary tree. e) State the output from a method public void pop () in Stack. f) List ONE (1) example of non-linear data structure. g) Define Tail recursive. (2 marks) (2 marks) (2 marks) (2 marks) (2 marks) (2 marks) (2 marks)