No plagarism please! Correct and detailed answer will be Upvoted else downvoted. Thank you! Q. Which of the following is CORRECT for the weighted interval scheduling problem? 1. The original problem...

No plagarism please!

Correct and detailed answer will be Upvoted else downvoted. Thank you!

Q. Which of the following is CORRECT for the weighted interval scheduling problem?

1. The original problem is one of the subproblems.

2. To ensure that a problem can be solved using dynamic programming, there should be a natural ordering on subproblems from “smallest” to “largest”. In the weighted interval scheduling problem, OPT(j) is a smaller problem than OPT(p(j))

3. The recursive implementation of the algorithm for computing the optimal value without using memoization has o(n) complexity

4. Weighted interval scheduling problem has exponential computing complexity.