1. The Hamiltonian cycles problem uses the following line of code to generate a
next vertex, provided x[ ] is a global array and kth vertex is under consideration:

x[k] (x[k] + 1) mod n

x[k] (x[k]) mod (n)

x[k] (x[k] + 1) mod (n+1)

x[k] x[k+1] mod n

x[k] (x[k] + 1) mod (n+1)

2. The graph colouringalgorithm’s time can be bounded by _________

O(mnm)

O(nm)

O(nm. 2n)

O(nmn).

O(nmn).

3. For 0/1 KNAPSACK problem, the algorithm takes ________ amount of time for
memory table, and ______time to determine the optimal load, for N objects and
W as the capacity of KNAPSACK.

O(N+W), O(NW)

O(NW),O(N+W)

O(N),O(NW)

O(NW),O(N)

O(NW),O(N+W)

4. Sorting is not possible by using which of the following methods?

Insertion

Selection

Deletion

Exchange

Deletion

5. What is the type of the algorithm used in solving the 8 Queens problem?

Backtracking

Dynamic

Branch and Bound

D and C

Backtracking

6. The following are the statements regarding the NP problems. Chose the right option
from the following options: I. All NP-complete problems are not NP-hard.
II. SomeNP-hard problems are not known to be NP-complete.

Both (I) and (II) are true

Both (I) and (II) are false

Only (I) is true

Only (II) is true

Only (II) is true

7. Let G be a graph with ‘n’ nodes and let ‘m’ be the chromatic number of the graph.
Then the time taken by the backtracking algorithm to color it is

O(nm)

O(n+m)

O(mnm)

O(nmn).

O(nmn).

8. The time complexity of the shortest path algorithm can be bounded by

O(n2)

O(n4)

O(n3)

O(n)

O(n log n ).

O(n3)

9. Read the following statements carefully and pick the correct option:
I. The worst time complexity of the Floyd’s algorithm is O(n3). II.
The worst time complexity of the Warshall’s algorithm is O(n3).

(I) is false but (II) is true

(I) is true but (II) is false

Both (I) and (II) are true

(I) is true and (II) is not true always

Both (I) and (II) are false.

Both (I) and (II) are true

10. Theasymptotic notation for defining the average time complexity is