S8 cOMPREHENSIVE VIVA ALGORITHM ANALYSIS AND DESIGN

Which of the following is not O(n²)?

• (15¹⁰) * n + 12099

• n^1.98

• n³/(sqrt(n))

• (2²⁰) * n

Which of the following is not a backtracking algorithm?

• Knight tour problem

• N queen problem

• Tower of hanoi

• M coloring problem

Suppose T(n) = 2T(n/2) + n, T(0) = T(1) = 1 Which one of the following is false.

• T(n) = O(n^2)

• T(n) = (nLogn)

• T(n) = (n^2)

• T(n) = O(nLogn)

What is the time complexity of Floyd–Warshall algorithm to calculate all pair shortest path in a graph with n vertices?

• O(n^2log(n))

• Theta(n^2log(n))

• Theta(n⁴)

• Theta(n³)

Four matrices M1, M2, M3 and M4 of dimensions pxq, qxr, rxs and sxt respectively can be multiplied is several ways with different number of total scalar multiplications. For example, when multiplied as ((M1 X M2) X (M3 X M4)), the total number of multiplications is pqr + rst + prt. When multiplied as (((M1 X M2) X M3) X M4), the total number of scalar multiplications is pqr + prs + pst. If p = 10, q = 100, r = 20, s = 5 and t = 80, then the number of scalar multiplications needed is

• 248000

• 44000

• 19000

• 25000

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 ,a2 ,a3 ,…,an} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array X, with n rows and W+1 columns. X[i, j],1 <= i <= n, 0 <= j <= W, is TRUE if and only if there is a subset of {a1 ,a2 ,...,ai} whose elements sum to j. Which of the following is valid for 2 <= i <= n and ai <= j <= W?

• X[i, j] = X[i - 1, j] ∨ X[i, j -ai]

• X[i, j] = X[i - 1, j] ∨ X[i - 1, j - ai]

• X[i, j] = X[i - 1, j] ∧ X[i, j - ai]

• X[i, j] = X[i - 1, j] ∧ X[i, j - ai

The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is 

• θ(n) 

• θ(logn) 

• θ(log*n) 

• θ(1) 

Which of the following is true about NP-Complete and NP-Hard problems.

• If we want to prove that a problem X is NP-Hard, we take a known NP-Hard problem Y and reduce Y to X

• The first problem that was proved as NP-complete was the circuit satisfiability problem.

• NP-complete is a subset of NP Hard

• All of the above

Let SHAM₃ be the problem of finding a Hamiltonian cycle in a graph G = (V,E) with V divisible by 3 and DHAM₃ be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

• Both DHAM₃ and SHAM₃ are NP-hard

• SHAM₃ is NP-hard, but DHAM₃ is not

• DHAM₃ is NP-hard, but SHAM₃ is not

• DHAM₃ is NP-hard, but SHAM₃ is not

The cube root of a natural number n is defined as the largest natural number m such that m³ ≤ n. The complexity of computing the cube root of n (n is represented in binary notation) is:

• O(n) but not O(n^0.5)

• O(n^0.5) but not O((log n)^k) for any constant k > 0

• O((log n)^k) for some constant k > 0, but not O ((log log n)^m) for any constant m > 0

• O((log log n)^m) for some constant k > 0.5, but not O((log log n)^0.5)