GATE CSE 2011 | Question: 25

Question

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 $L_i$, denote the length of the longest monotonically increasing sequence starting at index $i$ in the array.

Initialize $L_{n-1} = 1$.

For all $i$ such that $0 \leq i \leq n-2$

$ L_i = \begin{cases} 1+ L_{i+1} &  \quad\text{if A[i] < A[i+1]} \\ 1 & \quad\text{Otherwise}\end{cases} $

Finally, the length of the longest monotonically increasing sequence is $\text{max} \:(L_0, L_1, \dots , L_{n-1}).$

Which of the following statements is TRUE?

• A. The algorithm uses dynamic programming paradigm
• B. The algorithm has a linear complexity and uses branch and bound paradigm
• C. The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm
• D. The algorithm uses divide and conquer paradigm

Comments

How can I distinguish between option B : linear time complexity and option : A dynamic programming, just by looking at the  time complexity?

we can’t do it since here bottom-up dp approach also acting as linear time complexity

---

This is a dynamic programming paradigm, how?

dynamic programming == Careful bruteforces

in dynamic programming whenever we solve a problem we just stores its solution somewhere so that later we can use this solution to avoid recomputing that is what we are calling here Careful bruteforce meaning we are solving each and every subproblems but not doing recomputing.

we are bruteforcly solving for longest monotonicaly increasing sequence for every $i$ ( $0 <= i < n-2$ )

eg. $A = [1, 2, 3, 4, 4, 1, 4, 5]$

the longest monotonicaly increasing sequence is $[1, 2, 3, 4]$ 

 

when $i = 0$

         

so for $i = 0$ we have calculated & stored 3 subproblems $L[0], L[1]$ and $L[2]$ now for $i = 1, 2$ we don't need to recalculate it. we can start from $i = 3$.

 

conclusion: we are calculating for each $i$(bruteforce) but stroing its value(careful) so we do not rneed to ecompute later thus it is following the dynamic programmming paradigm.

---

1. Why it is Dynamic Programming (Option A)

The algorithm calculates the values of $L_i$ (the length of the longest monotonically increasing sequence starting at index $i$) by building on top of previously computed subproblems.

• Subproblem Dependency: To find $L_i$, the algorithm looks at the result of the next subproblem, $L_{i+1}$.

• Memoization/Tabulation: It stores these values (implicitly or explicitly in an array) and processes them from right to left (from $n-2$ down to $0$).

• Overlapping Subproblems & Optimal Substructure: These are the classic hallmarks of the Dynamic Programming paradigm.

Furthermore, because it iterates through the array exactly once from right to left, it computes each $L_i$ in $O(1)$ constant time. Thus, the overall time complexity is linear, i.e., $\mathcal{O}(n)$.

Answer 1

$(A)$ is the answer. 

The algorithm is storing the optimal solutions to subproblems at each point (for each $i$), and then using it to derive the optimal solution of a bigger problem. And that is dynamic programming approach. And the program has linear time complexity. 

http://stackoverflow.com/questions/1065433/what-is-dynamic-programming

Now, branch and bound comes when we explore all possible solutions (branch) and we backtrack as soon as we realise we won't get a solution (in classical backtracking we will retreat only when we won't find the solution). In backtracking : In each step, you check if this step satisfies all the conditions.
If it does : you continue generating subsequent solutions
If not : you go one step backward to check for another path

So, backtracking gives all possible solutions while branch and bound will give only the optimal one.

The given algorithm here is neither backtracking nor branch and bound. Because we are not branching anywhere in the solution space. 

And the algorithm is not divide and conquer as we are not dividing the problem and then merging the solution as in the case of merge sort (where merge is the conquer step). 

https://en.wikipedia.org/wiki/Divide_and_conquer_algorithms

Comments

i can view it as fibonacci solving with tabulation method..

---

The algorithm is taking 2n time, right? To reach 0 --> Ln-1 and the using those computed values to solve every sub problem from Ln-1--> 0

---

nice explaination sir

Answer 2

Answer: A

Note: It is strictly monotonic increasing. You have to start calculating from the last position of the array.

for(int i=n-2;i>=0;i--)
{
    if(A[i+1]>A[i])
    {
        L[i]=L[i-1]+1;
    }
    else L[i]=1;
}

It’s kind of finding nth Fibonacci number using dynamic programming where we start calculating from the first position of the array.

for(int i=2;i<=n;i++)
{
   arr[i]=arr[i-1]+arr[i-2];
}

both the problem is bottom-up dynamic programming. First looking at the "smaller" subproblems, and then solve the larger subproblems using the solution to the smaller problems.

Answer 3

Consider, Array A[0:5] where n=6.

Initialize L5=1.

now lets assume that the array is in strictly increasing order A={1,2,3,4,5,6}

now to compute L4={1+L5,if A[4]<A[5]}

else

if array A values are not in increasing order the L4=1.

so according to this we can assume that to compute L4 we need help of L5 to compute L3 we need help of L4 and so on.

So their is 1.Overlapping Subproblem 2.Recursive Equation 3.Optimal Substructure.

Basically they wanted to check your basic knowledge of Dynamic Programming concept.

Comments

this algorithm will give the longest monotonically increasing subarray(as the question asks about sequence )?

@UrbanCsGuy

Answer 4

This is a dynamic programming paradigm, how?

dynamic programming == Careful bruteforces

in dynamic programming whenever we solve a problem we just stores its solution somewhere so that later we can use this solution to avoid recomputing that is what we are calling here Careful bruteforce meaning we are solving each and every subproblems but not doing recomputing.

we are bruteforcly solving for longest monotonicaly increasing sequence for every $i$ ( $0 <= i < n-2$ )

eg. $A = [1, 2, 3, 4, 4, 1, 4, 5]$

the longest monotonicaly increasing sequence is $[1, 2, 3, 4]$ 

 

when $i = 0$

         

so for $i = 0$ we have calculated & stored 3 subproblems $L[0], L[1]$ and $L[2]$ now for $i = 1, 2$ we don't need to recalculate it. we can start from $i = 3$.

 

conclusion: we are calculating for each $i$(bruteforce) but stroing its value(careful) so we do not rneed to ecompute later thus it is following the dynamic programmming paradigm.