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 L_i 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(L₀, L₁, ......, L_n+1).
Which of the following statements is TRUE?

Answer
Comment
Array

Option : A
Explanation :
The Algorithm uses dynamic programming approach.

You must be logged in to post a comment.

You must be logged in to post a comment.

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 = _________.

Answer
Comment
Array

Option : A
Explanation :

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

You must be logged in to post a comment.

You must be logged in to post a comment.

58. A problem in NP is NP-complete if

Answer
Comment
Array

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.

You must be logged in to post a comment.

You must be logged in to post a comment.

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

Answer
Comment
Array

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

You must be logged in to post a comment.

You must be logged in to post a comment.

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

Answer
Comment
Array

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.

You must be logged in to post a comment.

You must be logged in to post a comment.

Related Quiz.
Algorithm Design Techniques

Forgot your password?

I agree with the Terms.