Time Left - 20:00 mins

GATE CS : Algorithms Champion Quiz 3

Attempt now to get your rank among 556 students!

Question 1

The concept of order (Big O) is important because

Question 2

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.

Question 3

Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?

Question 4

The usual Θ(n²) implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will

Question 5

Let

and

Then

is __________.

Question 6

Consider the following functions:
f(n)=2ⁿ
g(n)=n!
h(n)=n^logn
Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?

Question 7

Consider the following recurrence relation.
T(n) = T(n-1)+ 1/n if n>1
= 1 otherwise
What is the time complexity?

Question 8

Consider the following function:
int unknown(int n){
int i, j, k=0;
for (i=n/2; i<=n; i++)
for (j=2; j<=n; j=j*2)
k = k + n/2;
return (k);
}
The return value of the function is

Question 9

The recurrence equation
T (1) = 1
T (n) = 2T (n–1) + n, n ≥ 2
evaluates to

Question 10

The running time of an algorithm is represented by the following recurrence relation:

Which one of the following represents the time complexity of the algorithm?

556 attempts
0 upvotes
31 comments

Tags :

GATE & PSU CS Algorithms

Apr 5GATE & PSU CS