edited by
893 views
0 votes
0 votes

Consider the following statements:

  1. The running time of dynamic programming algorithm is always $\theta(\rho)$ where $\rho$ is number of subproblems
  2. When a recurrence relation has a 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 $\text{NP}$-hard problem, then $X$ must be $\text{NP}$-hard

Which of the statement(s) is (are) true?

  1. Only (ii) and (i)
  2. Only (ii)
  3. Only (ii) and (iii)
  4. Only (ii) and (iv)
edited by

1 Answer

2 votes
2 votes
$\underline{\textbf{Answer:}\Rightarrow}\;2)\;\text{only}\;b$

$\underline{\textbf{Explanation:}\Rightarrow}$

$\textbf{(i)False}$

The running time depends on the number of subproblems multiplied the time taken by each subproblem.

It will be true only in the case when the time taken by each subproblem $\mathbf{= O(1)}$.

$\textbf{(ii)True}$

$\because$ Cyclic dependency has mutually recursive modules. So, we cannot get a correct solution in DP.

$\mathbf{(iii) False}$

The reverse of the given statement is true, $\mathbf{i.e.}$ using Recursion and memoization it is faster.

$\mathbf{(iv) False}$

X must be $\textbf{NP-Complete}$ and not NP-hard.
edited by

Related questions

1 votes
1 votes
2 answers
1
4 votes
4 votes
6 answers
3
soujanyareddy13 asked May 12, 2021
1,865 views
The Boolean expression $AB+A \overline{B}+\overline{A}C+AC$ is unaffected by the value of the Boolean variable _________.$A$$B$$C$$A, B$ and $C$