The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+23 votes
2.7k views

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?

  1. The algorithm uses dynamic programming paradigm
  2. The algorithm has a linear complexity and uses branch and bound paradigm
  3. The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm
  4. The algorithm uses divide and conquer paradigm
asked in Algorithms by Veteran (107k points)
edited by | 2.7k views
+3
here dynamic programming is actually not applied.without using dynamic programming,we can't get linear time complexity here.because,there is no repeating subproblems.
0
how can u say there are no repeating subproblems,  while solving longest increasing subsequence, first u calculate the subsequence of length 1, then length 2 and so on.... and while solving subsequences of length n+1, u are using the information where u have solved the longest subsequence of length n, hence repeating subproblems and hence Dynamic Programming.
0

this given algo is not taking help of dynamic programming.if we need to take the advantage of dynamic programming here,then we have to start calculating values from Ln-1 up to 0.but here they are computing from 0 to Ln-1.

0
It is using optimal substructure , As finally it is going for a optimal solution
0
Can you please explain the optimal substructure for thiss??
+8

This might help ...

0
thank you @puja
0

Sambit Kumar there are no such prerequisites for dynamic programming that it has to be solved  by computing from Ln-1 up to 0. It can be applied in both top-down or bottom-up ways.

Refer:https://www.codechef.com/wiki/tutorial-dynamic-programming

https://www.geeksforgeeks.org/tabulation-vs-memoizatation/

1 Answer

+40 votes
Best answer

$(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. http://www.cs.cornell.edu/~wdtseng/icpc/notes/bt2.pdf

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

answered by Veteran (363k points)
edited by
0

@arjun Sir 

how the program has linear time complexity .As per my knowledge the best algo present to find longest increasing subsequence is O(n logn) time.

0
Sir , I have gone through this link and it is mentioned that its O(nlogn) time ,so how is it implemented using dynamic programming.

http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
0
@Abhishek The algorithm is given in question. Now you can see if it is finding the "longest monotonically increasing sequence or not".

@Radha You can compare the algos- they are both solving different problems.
+2
Arjun sir, I think it's finding the longest subsequence which is present contiguously. Ideally subsequence need not have contiguous elements. Am I right?
0
yes

but in the given algorithm where 2 strings are comparing here?
0

Sir I dont think this is correct answer... As someone has commented above

"this given algo is not taking help of dynamic programming.if we need to take the advantage of dynamic programming here,then we have to start calculating values from Ln-1 up to 0.but here they are computing from 0 to Ln-1."

This should not be dynamic programming. It looks like Brute Force approach to me.. Please check the question and ur answer again... Correct me if I am wrong

0
@anchit where have you seen such a requirement for dynamic programming?
0

@Arjun sir :-

1.The sequence will be of continues ,right?We cannot get subsequence as this algo do not work for that?

2.But here what do the word monotonically means in question?My thinking is that if two elements are same then they should both be considered as part of sequence but the algo checks for strictly increasing sequence.

+2
@ sushmita

here increasing sequence is asked not subsequence, sequence is always contiguous.
+1

For branch and bound concept  ....

For Backtracking Concept

+1
0

@anchitjindal07, @Sambit Kumar

if we need to take the advantage of dynamic programming here,then we have to start calculating values from Ln-1 up to 0.but here they are computing from 0 to Ln-1.

Though that is not the criteria to identify whether a problem can be solved using DP, still if you want to take help of previously computed result then make the L of higher index as the previously computed one. What i mean to say is lets start from index(n-2) and go backwards. In that way we can use the recurrence relation given in the question.

L[n-1]=1

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

 

Doubt : 

"longest monotonically increasing sequence" 

and the given recurrence relation has condition Li=1+Li+1 where A[i]<A[i+1]. Why not ?

Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,699 questions
48,662 answers
156,606 comments
63,970 users