Follow Us :

Algorithms - Algorithm Design Techniques

Avatto > > GATE COMPUTER SCIENCE > > Practice Questions > > Computer Science And Information Technology > > Algorithms > > Algorithm Design Techniques

61. 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
  • Explanation :
    1. We can use “Depth First Search” Algorithm, to check it there is a cycle is an undirected graph. I t we encounter any “back edge” in “Depth first search” then given undirected graph has a cycle. Also, If there is a cycle in the Undirected graph, we must encounter a “back edge” in DFS. And, DFS can be done in O(| E| + | V| ) time for graph G = (V, E). So, it can is in F.
    2. P ≤ NP, So, it is also in NP.
    3. NP - complete problem A ∈ NP. By, Definition Every problem in NP can be solved in polynomial time using non-deterministic turing machine.
    So, Answer is (A) i.e. 1, 2, and 3 are true.
Cancel reply
Cancel reply

62. Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the foliowing represents the correct Venn diagram of the complexity classes P, NP and NP Complete(NPC)?

  • Option : D
  • Explanation :
    The most important open question in complexity t heor y is whether the P = NP, which asks whether polynomial time algorithms actually exist for NP-complete and all NP problems (since a problem “C” is in NP-complete, iff C is in NP and every problem in NP is reducible to C in polynomial time). In the given question it is given that some polynomial time algorithm exists which computes the largest clique problem in the given graph which is known NP-complete problem. Hence P = NP = NP-Complete.
Cancel reply
Cancel reply

63. Consider the decision problem 2CNFSAT defined as follows:
{Φ|Φ is a satisfiable propositional formula in CNF with at most two literals per clause}
For example, Φ = (x1 ∨ x2) ∧ (x1 ∨ x3) ∧ (x2 ∨ x4) is a Boolean formula and it is in 2CNFSAT. The" decision problem 2CNFSAT is

  • Option : B
  • Explanation :
    2CNF SAT can be solvable in polynomial time by reduction to directed graph reach ability.
Cancel reply
Cancel reply

64. Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3-SAT and 3- SAT reduces in polynomial time to Q2. Then which one of the following is consistent with the above statement?

  • Option : A
  • Explanation :
    Q1 is in NP and Q2 is in NP-hard
Cancel reply
Cancel reply

65. Language L1 is polynomial time reducible to language L2 Language L3 is polynomial time reducible to L2, which in turn is polynomial time reducible to language L4. Which of the following is/are True?
I. If L4 ∈ P, L2 ∈ P
II. If L1 ∈ P or L3 ∈ P, then L2 ∈ P
III.L1 ∈ P or if and only if L3 ∈ P
IV. If L4 ∈ P then L1 ∈ P, then L3 ∈ P

  • Option : C
  • Explanation :
         L2 ≤ pL4
         L1 ≤ pL2
    If    L4 ∈ P
    then  L2 ∈ P
         L1 ∈ P,
Cancel reply
Cancel reply
Related Quiz.
Algorithm Design Techniques