edited by
15,136 views
43 votes
43 votes

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
edited by

3 Answers

Best answer
71 votes
71 votes

$(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

edited by
4 votes
4 votes

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.

edited by
2 votes
2 votes
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.
Answer:

Related questions

14 votes
14 votes
2 answers
3
go_editor asked Sep 29, 2014
4,762 views
Choose the most appropriate word(s) from the options given below to complete the following sentence.I contemplated _________ Singapore for my vacation but decided against...
36 votes
36 votes
6 answers
4
go_editor asked Sep 29, 2014
10,713 views
A deterministic finite automaton ($\text{DFA}$) $D$ with alphabet $\Sigma = \{a, b\}$ is given below.Which of the following finite state machines is a valid minimal $\tex...