We wish to find the length of the longest common sub-sequence (LCS) of X[m] and
Y[n] as c(m,n), where an incomplete recursive definition for the function c(i,j) to
compute the length of the LCS of X[m] and Y[n] is given below :
cli,jJ=0, if either i=0 or j=0

=exprl1, if i,j > O and X[i-1]=Y[j—1]

=expr2, if i,j > O and X[i-1]#Y[j—-1]
Which one of the following options is correct ?

A:-expr1=0

B:-expr1=1+c[i-1,j]
C:-expr2=max{cli-1, j—1],cli+1,j]}
D:-expr2=max{cli—1, j],cli,j—1]}
Correct Answer:- Option-D

Question39:-What is true about Greedy Algorithms ?

1. It makes a locally optimal choice in the hope that this choice will lead to a
globally optimal solution.

2. Always yield optimal solutions.

3. Generally faster than dynamic programming.

A:-1 only

B:-1 and 2 only

C:-1 and 3 only

D:-All 1, 2 and 3

Correct Answer:- Option-C
Question40:-Which of the following is not example of NP Complete problem ?

A:-Travelling salesperson problem

B:-Halting problem

C:-Subset sum problem

D:-Vertex cover problem

Correct Answer:- Option-B

Question41:-How many tokens are there in the following C programming language
statement ?

printf("%d+%d=%d",a,b,c);
A:-18
8:-15
C:-11
D:-20
Correct Answer:- Option-C

Question42:-Which of the following class of automata is used for parsing in a
compiler ?

A:-Finite State Automata

B:-Push Down Automata