Consider the following statements, which of the statement(s) is/are FALSE?
-
The running time of dynamic programming algorithm is always θ (p) where p is number of subproblems
-
When a recurrence relation has cyclic dependency, it is impossible to use that recurrence relation (unmodified) in a correct dynamic program
-
For a dynamic programming algorithm computing all values in a bottom up fashion is asymptotically faster than using recursion and memorization
-
If a problem X can be reduced to a known NP hard problem, then X must be NP-hard
