Register

TIFR CSE 2017 | Part B | Question: 2

• edited by
1,713 views
5 5 votes

Consider the following statements:

  1. Checking if a given $undirected$ graph has a cycle is in $\mathsf{P}$
  2. Checking if a given $undirected$ graph has a cycle is in $\mathsf{NP}$
  3. Checking if a given $directed$ graph has a cycle is in $\mathsf{P}$
  4. Checking if a given $directed$ graph has a cycle is in $\mathsf{NP}$

Which of the above statements is/are TRUE? Choose from the following options.

  1. Only i and ii
  2. Only ii and iv
  3. Only ii, iii, and iv
  4. Only i, ii and iv
  5. All of them

1 Answer

Voting & Accepting an answer helps improve the community
Answer:
← Previous · Minimal DFANext → · TIFR CSE 2017 | Part...
← Previous in category · TIFR CSE 2017 | Part...Next in category → · TIFR CSE 2017 | Part...
Position:
Show:

Related questions

5 5 votes
1 1 answer
1.7k
1.7k views
go_editor asked Dec 23, 2016
1,650 views
TIFR CSE 2017 | Part B | Question: 15
A multivariate polynomial in $n$ variables with integer coefficients has a binary root if it is possible to assign each variable either 0 or 1, so that the polynomial eva...
16 16 votes
2 answers 2 answers
4.9k
4.9k views
go_editor asked Dec 23, 2016
4,891 views
TIFR CSE 2017 | Part B | Question: 7
An array of $n$ distinct elements is said to be un-sorted if for every index $i$ such that $ 2 \leq i \leq n-1$, either $A[i] \text{max} \{A [i-1], A[i+1]\}$, or $A[i] <...
15 15 votes
4 answers 4 answers
3.4k
3.4k views
go_editor asked Dec 23, 2016
3,434 views
TIFR CSE 2017 | Part A | Question: 15
Let $T(a, b)$ be the function with two arguments (both nonnegative integral powers of 2) defined by the following recurrence:$ T(a, b) = T \left( \frac{a}{2}, b \right) +...
9 9 votes
1 answers 1 answer
2.3k
2.3k views
go_editor asked Dec 22, 2016
2,265 views
TIFR CSE 2017 | Part A | Question: 12
Consider the following program modifying an $n \times n$ square matrix $A$:for i=1 to n: for j=1 to n: temp=A[i][j]+10 A[i][j]=A[j][i] A[j][i]=temp-10 end for end forWhic...