engineering recuitment GATE CSE 2023-24 Test Series Algorithms Algorithm Design Techniques Dynamic Programming
Consider the following statements, which of the statement(s) is/are FALSE?
1
The running time of dynamic programming algorithm is always θ (p) where p is number of subproblems
2
When a recurrence relation has cyclic dependency, it is impossible to use that recurrence relation (unmodified) in a correct dynamic program
3
For a dynamic programming algorithm computing all values in a bottom up fashion is asymptotically faster than using recursion and memorization
4
If a problem X can be reduced to a known NP hard problem, then X must be NP-hard