Algorithms MCQ - 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?

The Algorithm uses dynamic programming approach.

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

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

58 A problem in NP is NP-complete if

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.

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

By definition X is in NP, but not necessarily NP Complete

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

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.