Aspire's Library
Study Stuff for MCA Examinations - NIMCET
Previous Year Question (PYQs)
Consider the following statements:
(a) The running time of dynamic programming algorithm is always $\theta(\rho)$ where $\rho$ 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.
(d) If a problem $X$ can be reduced to a known NP-hard problem, then $X$ must be NP-hard.
Which of the statement(s) is/are true?
Solution
Statement (a) is false because running time also depends on the time required to solve each subproblem, not only the number of subproblems.
Statement (b) is true because cyclic dependency creates a circular dependency, so the recurrence cannot be used directly in a correct dynamic program.
Statement (c) is false because bottom-up DP and memoized recursion usually have the same asymptotic time complexity.
Statement (d) is false because if $X$ is reduced to an NP-hard problem, it does not prove that $X$ is NP-hard. To prove $X$ is NP-hard, a known NP-hard problem should be reduced to $X$.
So, only statement (b) is true.
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
