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.

Let X be a problem that belongs to the class NP. Then which one of the following is TRUE?

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?

To which class does the Euler’s circuit problem belong?

How many stages of procedure does a non-deterministic algorithm consist of?

A non-deterministic algorithm is said to be non-deterministic polynomial if the time-efficiency of its verification stage is polynomial.

Problems that can be solved in polynomial time are known as traceable problems

CNF-satisfiability problem belongs to

Approximation algorithms are used for finding exact solution for optimisation problems

can approximation algorithm be used for solving decision problem

Which among the followings are polynomial time

Which of the following problems has the algorithm that solves by polynomial time

Which of the following algorithm produces the same output for given the same input every time

The time complexity of the following C function is

int recursive (mt n)

{

if (n == 1)

return (1);

else

return (recursive (n-1) + recursive (n-1));

}

Which of the following algorithm has the running time of $$\Theta\left(n^3\right)$$  

Running time of any approximation algorithms is

The problem is said to be NP complete if and only if

The set of problems that can be solved in polynomial time is ------------------------

The set of decision problems that can be verified in polynomial time but necessarily solvable in polynomial time is ------------ Problems

------------------------ problems have exponential time solutions

Graph Coloring Problem is an example of ------------------- problem

Traveling Sales Man Problem is the best example of NP-Hard problem

Which is the hardest Problem ?

Binary and Linear Search is the example of ----------- Problem

Which is quicker to verify and slow to solve ?

If any problem has Non-deterministic polynomial solution then it is both ____ and ___

________ is a subgraph of a graph such that all the vertices in this subgraph are connected with each other that is the subgraph is a complete graph.

Dijkstra’s Algorithm cannot be applied on

_________ is the class of decision problems that can be solved by non-deterministic polynomial algorithms?

What is the time complexity of this code

int a = 0, i = N;

while (i > 0)

{

a += i;

i /= 2;

}

Time Complexity of this program:

def f():

a = 0

for i = 1 to n:

a += i;

b = 0

for i = 1 to m:

b += i;

What is the time complexity of following code:

int a = 0;

for (i = 0; i < N; i++) {

for (j = N; j > i; j--) {

a = a + i + j;

}

}

What is the time complexity of following code:

int i, j, k = 0;

for (i = n / 2; i <= n; i++) {

for (j = 2; j <= n; j = j * 2) {

k = k + n / 2;

}

}

Let f(n) and g(n) be two non-negative functions,f(n)=O(g(n)) if and only if..........................

Let f(n) and g(n) be two non-negative functions,f(n)= $$\omega$$  (g(n)) if and only if..........................

Let f(n) and g(n) be two non-negative functions,f(n)=  $$\theta$$  (g(n)) if and only if..........................

...................................are the characteristics of an algorithm

Find the time complexity for the following algorithm using step count method.

Algorithm sum(a,n)

{

nsum=0;

for(i=1;i<=n;i++)

{

nsum=nsum+a[i];

}

}

Find the space complexity for the following algorithm

Algorithm sum(a,b,c)

{

a=10;

b=20;

c=30;

d=a+b+c;

}

What does the following piece of code do?

for (int i = 0; i < arr.length-1; i++) {

for (int j = i+1; j < arr.length; j++) {

if( (arr[i].equals(arr[j])) && (i != j) ) {

System.out.println(arr[i]);

}

}

}

From the following given tree, what is the code word for the character ‘a’?