Answer Happy

6. [Min Element Sum.] Consider the following problem, MinElement Sum. MinElementSum(n,S): Let S be a set of positive integers, and let n be a non-negative integer. Find the minimal number of elements of S needed to write n as a sum of elements of S (possibly with repetitions). If there is no way to write n as a sum of elements of S, return None For example, if S = {1,4,7} and n = 10, then we can write n=1+1+1+ 7 and that uses four elements of S. The solution to the problem would be "4." On the other hand if S = {4,7} and n = 10, then the solution to the problem would be "None," because there is no way to make 10 out of 4 and 7. Your friend has devised a divide-and-conquer algorithm to solve MinElementsum. Their pseudocode is below: def minElementSum(n, S): if n == 0: return o if n <min(S): return None candidates = [] for s in S: cand = minElementSum(n-s, S) if cand is not None : candidates.append( cand + 1 ) if len(candidates) == 0: return None return min(candidates) Your friend's algorithm correctly solves MinElementsum. Before you start doing the problems on the next page, it would be a good idea to walk through the algorithm and to understand what this algorithm is doing and why it works.

(a) Argue that for S = {1, 2}, your friend's algorithm has exponential running time. (That is, running time of the form 287(n)). You may assume that Fibonacci numbers grow exponentially, i.e., let f(n) be a function that returns n-th Fibonacci number, you may assume that f(n) = 232(7) We are expecting: • A recurrence relation that the running time of your friend's algorithm satisfies when S = {1, 2} A convincing argument that the closed form for this expression is 28(m). You do not need to write a formal proof. ] (b) Turn your friend's algorithm into a top-down dynamic programming algorithm. Your algorithm should take time O(ns). Hint: Add an array to the pseudoco de above to prevent it from solving the same sub-problem repeatedly. [We are expecting: • Pseudocode AND a short English description of the idea of your algorithm. An informal justification of the running time. (c) Turn your friend's algorithm into a bottom-up dynamic programming algorithm. Your algorithm should take time O(ns). Hint: Fill in the array you used in part (b) iteratively, from the bottom up. [We are expecting: • Pseudocode AND a short English description of the idea of your algorithm • An informal justification of the running time.