CompilerDesign
October 7, 2023NICNIELIT ScientistB 2020
October 8, 2023UGCNET DEC2019 Part2
Question 1

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 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 bottomup fashion is asymptotically faster than using recursion and memorization.
(d) If a problem X can be reduced to a known NPhard problem, then X must be NPhard.
Which of the statement(s) is (are) true?
(a) The running time of dynamic programming algorithm is always θ(ρ) where ρ 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 bottomup fashion is asymptotically faster than using recursion and memorization.
(d) If a problem X can be reduced to a known NPhard problem, then X must be NPhard.
Which of the statement(s) is (are) true?
Only (b) and (a)


Only (b)


Only (b) and (c)


Only (b) and (d)

Question 1 Explanation:
(i). FALSE: The running time of a dynamic program is the number of subproblems times the time per subproblem. This would only be true if the time per subproblem is O(1).
(ii). TRUE: Cyclic dependency is a relation between two or more modules which either directly or indirectly depend on each other to function properly. Such modules are also known as mutually recursive. So, we can’t get correct solution when we are using dynamic programming.
(iii). FALSE: A bottom up implementation must go through all of the subproblems and spend the time per subproblem for each. Using recursion and memoization only spends time on the subproblems that it needs. In fact, the reverse may be true: using recursion and memoization may be asymptotically faster then a bottomup implementation.
(iv). FALSE: If a problem X can be reduced to a known NPhard problem, then X must be NPComplete.
(ii). TRUE: Cyclic dependency is a relation between two or more modules which either directly or indirectly depend on each other to function properly. Such modules are also known as mutually recursive. So, we can’t get correct solution when we are using dynamic programming.
(iii). FALSE: A bottom up implementation must go through all of the subproblems and spend the time per subproblem for each. Using recursion and memoization only spends time on the subproblems that it needs. In fact, the reverse may be true: using recursion and memoization may be asymptotically faster then a bottomup implementation.
(iv). FALSE: If a problem X can be reduced to a known NPhard problem, then X must be NPComplete.
Correct Answer: B
Question 1 Explanation:
(i). FALSE: The running time of a dynamic program is the number of subproblems times the time per subproblem. This would only be true if the time per subproblem is O(1).
(ii). TRUE: Cyclic dependency is a relation between two or more modules which either directly or indirectly depend on each other to function properly. Such modules are also known as mutually recursive. So, we can’t get correct solution when we are using dynamic programming.
(iii). FALSE: A bottom up implementation must go through all of the subproblems and spend the time per subproblem for each. Using recursion and memoization only spends time on the subproblems that it needs. In fact, the reverse may be true: using recursion and memoization may be asymptotically faster then a bottomup implementation.
(iv). FALSE: If a problem X can be reduced to a known NPhard problem, then X must be NPComplete.
(ii). TRUE: Cyclic dependency is a relation between two or more modules which either directly or indirectly depend on each other to function properly. Such modules are also known as mutually recursive. So, we can’t get correct solution when we are using dynamic programming.
(iii). FALSE: A bottom up implementation must go through all of the subproblems and spend the time per subproblem for each. Using recursion and memoization only spends time on the subproblems that it needs. In fact, the reverse may be true: using recursion and memoization may be asymptotically faster then a bottomup implementation.
(iv). FALSE: If a problem X can be reduced to a known NPhard problem, then X must be NPComplete.
Subscribe
Login
0 Comments