Consider the following statements :

(a) The running time of dynamic programming θ(ρ) ρ algorithm is alway where is number of subproblems.

(b) When a recurrence relation has cyclic dependency, it is impossible to use that recurrence relation (unmodified) in a correct dynamic program.

(c) For a dynamic programming algorithm, computing all values in a bottom-up fashion is asymptotically faster than using recursion and memorization. X

(d) If a problem can be reduced to a known X NP-hard problem, then must be NP-hard. Which of the statement(s) is (are) true?

1. AOnly (b) and (a)
2. BOnly (b)
3. COnly (b) and (c)
4. DOnly (b) and (d)

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: B. Only (b)

Explanation

Only (b) is true: a recurrence with cyclic dependencies cannot be evaluated directly by DP. Running time also depends on work per subproblem (a false); bottom-up and memoized versions have the same asymptotics (c false); reducing X to an NP-hard problem says nothing about X's hardness (d false).