Consider the following statements: (a) The running time of dynamic programming…
2019
Consider the following statements:
(a) The running time of dynamic programming algorithm is always 𝜃(𝜌) where 𝜌 is number of subproblems
(b) When a recurrence relation has a 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 𝑋 can be reduced to a known NP-hard problem, then 𝑋 must be NP-hard
Which of the statement(s) is (are) true?
- A.
Only (b) and (a)
- B.
Only (b)
- C.
Only (b) and (c)
- D.
Only (b) and (d)
Attempted by 61 students.
Show answer & explanation
Correct answer: B
Answer: Only statement (b) is true.
(a) False: the running time of a dynamic programming algorithm is not always Θ(ρ). Each subproblem may require more than constant time to compute, so the total time is Θ(number of subproblems × time per subproblem).
(b) True: a cyclic dependency in the recurrence means values depend circularly, so you cannot directly use that recurrence (unmodified) in a standard top-down or bottom-up dynamic program. The recurrence must be rewritten, solved simultaneously, or handled by a different approach.
(c) False: bottom-up tabulation and top-down memoization typically compute the same set of subproblems and therefore have the same asymptotic complexity. Bottom-up may have lower constant overhead in some cases, but it is not asymptotically faster in general.
(d) False: the implication is reversed. If a known NP-hard problem reduces to X, then X is NP-hard. If X reduces to a known NP-hard problem, that only shows X is no harder than that NP-hard problem and does not prove X is NP-hard.
Conclusion: Only statement (b) is true.
A video solution is available for this question — log in and enroll to watch it.