Answer Happy

Divide-and-Conquer • Q2(14 points): Suppose that a computer does not know how to apply dynamic programming techniques to compute a function f(n), but it knows how to use the divide and Conquer approach to compute f(n) as follows. The computer takes only constant time for scalar arithmetic operations. f(n) = { Divide: Do nothing. Conquer: Combine: if n = 0 if n = 1 f(n-1) + f(n − 2) +n if n>1 (a) (10 points) Please write down the three steps of Divide, Conquer and Combine to de- scribe how the computer calculates f(n). 1 (b)(4 points) Please write down the running time recurrence if f(n) is computed using the above approach.