Follow Us :

Algorithms - Algorithm Design Techniques

Avatto > > GATE COMPUTER SCIENCE > > Practice Questions > > Computer Science And Information Technology > > Algorithms > > Algorithm Design Techniques

56. 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 denotes 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?

  • Option : A
  • Explanation :
    The Algorithm uses dynamic programming approach.
Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


57. Consider two strings A = "qpqrr" and B = "pqprqrp". Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of such longest common subsequences between A and B.
Then x +10y = _________.

  • Option : A
  • Explanation :

    Longest common subsequence : qpqr
    x + 10y = 4 + 10 × 3 = 34
Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


58. A problem in NP is NP-complete if

  • Option : B
  • Explanation :
    A problem in NP becomes NP – C if all NP problems can be reduced to it in polynomial time. This is same as reducing any of the NPC to it. 3-SAT is an NP-C problem, reducing it to a NP Problem would means that NP Problem is NP – C.
Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


59. For problems X and Y, Y is NP-complete and X reduces to Y in polynomial time. Which of the following is TRUE?

  • Option : D
  • Explanation :
    By definition X is in NP, but not necessarily NP Complete
Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


60. Let πA be a problem that belongs to the class NP.
Then which one of the following is TRUE?

  • Option : D
  • Explanation :
    If πA is NP-hard, then it is NP-complete
    Alternately
    πA be a problem (given) in class NP. we say that πA is NP complete if the following statements are true about L.
    (1) πA is in NP
    (2) For every πA'in NP there is polynomial time reduction of πA' to πA.
Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


Related Quiz.
Algorithm Design Techniques