Higher-Education-and-Politics
March 14, 2025GATE 2011
March 14, 2025GATE 2011
|
Question 12
|
An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0:n-1] is given below. Let Li denote the length of the longest monotonically increasing sequence starting at index i in the array
Initialize Ln-1=1. For all i such that 0≤i≤n-2
Finally the length of the longest monotonically increasing sequence is Max(L0, L1, …, Ln-1).
Which of the following statements is TRUE?
|
The algorithm uses dynamic programming paradigm
|
|
|
The algorithm has a linear complexity and uses branch and bound paradigm
|
|
|
The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm
|
|
|
The algorithm uses divide and conquer paradigm
|
Question 12 Explanation:
Key Note of Dynamic programming:
1. Dynamic programming is when you use past knowledge to make solving a future problem easier.
2. Dynamic programming is a technique used to avoid computing multiple time the same sub-problem in a recursive algorithm.
Note: It is neither backtracking nor branch and bound because we are not branching anywhere in the solution space. The algorithm is not divide and conquer as we are not dividing the problem and then merging the solution
1. Dynamic programming is when you use past knowledge to make solving a future problem easier.
2. Dynamic programming is a technique used to avoid computing multiple time the same sub-problem in a recursive algorithm.
Note: It is neither backtracking nor branch and bound because we are not branching anywhere in the solution space. The algorithm is not divide and conquer as we are not dividing the problem and then merging the solution
Correct Answer: A
Question 12 Explanation:
Key Note of Dynamic programming:
1. Dynamic programming is when you use past knowledge to make solving a future problem easier.
2. Dynamic programming is a technique used to avoid computing multiple time the same sub-problem in a recursive algorithm.
Note: It is neither backtracking nor branch and bound because we are not branching anywhere in the solution space. The algorithm is not divide and conquer as we are not dividing the problem and then merging the solution
1. Dynamic programming is when you use past knowledge to make solving a future problem easier.
2. Dynamic programming is a technique used to avoid computing multiple time the same sub-problem in a recursive algorithm.
Note: It is neither backtracking nor branch and bound because we are not branching anywhere in the solution space. The algorithm is not divide and conquer as we are not dividing the problem and then merging the solution
Subscribe
Login
0 Comments