78.

79.

80.

81.

82.

84.

85.

123/2016
The Knapsack problem where the objective function is to minimize 179 ೧7೦11! 15
A) Greedy B) Dynamic
©) Back tracking D) Branch and Bound

Choose the correct answer for the following statements :

|. NP problem can run in polynomial time on a non-deterministic turing machine.
Il. All NP complete problem are NP-Hard.

A) lis false and Il is true B) lis true and Il is false
C) Both are false D) Both are true

A Hamiltonian cycle in a Hamiltonian graph of order 24 has

A) 12 edges 8( 23 5

C) 24 edges D) None of the above

Which of the following is not a group ?

A) The integers under addition

B) The non-zero integers under multiplication

C) The non-zero real numbers under multiplication
D) The complex numbers under addition

The binary relation R={(0, 0), (1, 1)}on A={0, 1, 2, 8} is
A) Reflexive, Not Symmetric, Transitive

B) Not Reflexive, Symmetric, Transitive

C) Reflexive, Symmetric, Not Transitive

D) Reflexive, Not Symmetric, Not Transitive

. LetR={(a,a), (a,b), (b, b). (a,c), (c, c)} be a partial order relation on X ={a, b, c}. Let'<="

be the corresponding lexicographic order on £ .. Which of the following is true ?
A) bc<=ba B) abbac <= abb
C) abbac <= abbab D) abbaaacc <= abbaab

What is the language of the grammar with the following production rules ?
8 ‏٤‎

ج لم

‎ne N}‏ | 600 8[ زم

‎8) (०० | € {8} * }

‎©) (© | # € {9} * }

‎D) All of the answers above are incorrect

‎Which of the following is not decidable ?

‎A) Given a turing machine M, a string S and an integer k, M accepts S within k steps
B) Equivalence of two given turing machines

‎C) Language accepted by a given finite state machine is not empty

‎D) Language generated by a context free grammar is not empty

‎-13-

‎