Gate Exam

Which of the following statements are TRUE?
(1) The problem of determining whether there exists a cycle in an undirected
graph is in P.
(2) The problem of determining whether there exists a cycle in an undirected
graph is in NP.
(3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.

Option
(A) 1,2 and 3
(B) 1 and 2 only
(C) 2 and 3 only
(D) 1 and 3 only

Read Solution (Total 0)

Gate Other Question
In a k-way set associative cache, the cache is divided into v sets, each of which
consists of k lines. The lines of a set are placed in sequence one after another.
The lines in set s are sequenced before the lines in set (s+1). The main memory
blocks are numbered 0 onwards. The main memory block numbered j must be
mapped to any one of the cache lines from
(A) (j mod v) *k to (j mod v) *k + (k − 1)
(B) (j mod v) to (j mod v) + (k − 1)
(C) (j mod k) to ( j mod k) + (v − 1)
(D) (j mod k) * v to ( j mod k) * v + (v − 1) Which of the following statements is/are FALSE?
(1) For every non-deterministic Turing machine, there exists an equivalent
deterministic Turing machine.
(2) Turing recognizable languages are closed under union and complementation.
(3) Turing decidable languages are closed under intersection and
complementation
(4) Turing recognizable languages are closed under union and intersection.

Option
(A) 1 and 4 only
(B) 1 and 3 only
(C) 2 only
(D) 3 only