Mock 7 – Complexity, Recurrences & Divide and Conquer (Part 2)

Match List I (recurrence) with List II (complexity). List I: (A) T(n) = 2T(n/2) + n, (B) T(n) = T(n/2) + 1, (C) T(n) = 2T(n/2) + 1, (D) T(n) = T(n−1) + n. List II: (I) T(n) = Θ(n log n) (exact), (II) O(n²), (III) T(n) = Θ(n) (exact), (IV) O(n).

Let n be the least integer such that f(x) is O(xⁿ). Arrange the following functions in increasing order of n: A. f(x) = 3x³ + (log x)⁴ B. f(x) = (x⁵ + x² + 1)/(x³ + 1) C. f(x) = (x³ + x² + 1)/(x² + 1) D. f(x) = (x² + 5 log x)/(x² + 1)

Match List I with List II. List I: A. Parallel FFT, B. Iterative FFT, C. Evaluation of a polynomial at n points by Horner's method, D. Product of two polynomials represented in point-value form. List II: I. Θ(n²), II. Θ(n), III. Θ(lg n), IV. Θ(n lg n).

Let f(n) and g(n) be asymptotically positive functions. Statement I: f(n) ≥ 1 and f(n) = O(g(n)) ⇒ g(n) = Ω(f(n)). Statement II: f(n) = O(g(n)) ⇒ lg(f(n)) = O(lg(g(n))), where lg(g(n)) ≥ 1 and f(n) ≥ 1 for all sufficiently large n. Choose the most appropriate answer.

A. If some NP-complete problem P is in 𝒫, then 𝒫 = 𝒩𝒫. B. TSP is in 𝒩𝒫. C. SAT is in 𝒩𝒫. D. The Hamiltonian circuit problem is not NP-complete. Which are correct?

Match List I with List II

Given below are two statements:

Statement I: If f and g are two functions and f = O(g) g ≠ o(f) but , we say that the growth rate of g is smaller than that of f

Statement II: The class of all decision problems decided by a TM in exponential time, that is O(2k) k , being a constant. In the light of the above statements, choose the most appropriate answer from the options given below.

For matrix multiplication with a simple divide-and-conquer algorithm: A. the running time is T(n) = Θ(n³) B. the running time is T(n) = Θ(n² log n) C. the recurrence is T(n) = 8T(n/2) + Θ(n²) D. the recurrence is T(n) = 8T(2n) + Θ(n² log n) E. one of the cases of the master theorem applies

Given the FFT we can have ______ time procedure for multiplying two polynomials A(x) Q and B(x) of degree bound n where input and output representations are in coefficient form, assuming n is a power of 2.

Circuit satisfiability problem: given a Boolean combinational circuit of AND, OR and NOT gates, is it satisfiable (is there an input for which the output is 1)? 1. Circuit-SAT belongs to NP. 2. Circuit-SAT is at least as hard as any language in NP. 3. Circuit-SAT is NP-complete. 4. The size of the circuit is Θ(k² + 1). 5. If P ≠ NP, this would contradict the NP-completeness of the problem.

The solution of the recurrence T(n) = 3T(n/4) + n log n is

Match each algorithm with its running time. (A) Breadth-first search, (B) Rabin–Karp algorithm, (C) Depth-first search, (D) Heap sort (worst case), (E) Quick sort (worst case). Times: (I) Θ(V + E), (II) O(V + E), (III) Θ((n − m + 1)m), (IV) O(n²), (V) O(n log n).

Statement I: Vertex cover has a polynomial-time 2-approximation algorithm. Statement II: TSP-tour is a polynomial-time 3-approximation algorithm for the travelling salesman problem with the triangle inequality. Which is correct?

A data structure is required for storing a set of integers such that each of the following O(log n) operations can be done in time, where n is the number of elements in the set. Deletion of the smallest element Insertion of an element if it is not already present in the set Which of the following data structures can be used for this purpose?

Which of the given options provides the increasing order of asymptotic complexity of f1, f2, f3 f4 functions and ? f1(n) = 2n A. f2(n) = n3/2 B. f3(n) = n log n C. f4(n) = nlog n D.

The running time of an algorithm is O(g(n)) if and only if:

(A) its worst-case running time is O(g(n)) and its best-case running time is Ω(g(n)).

(B) its worst-case running time is Ω(g(n)) and its best-case running time is O(g(n)).

(C) O(g(n))=Ω(g(n)) (O= big O).

(D) o(g(n))∩ω(g(n)) is non-empty. (o= small o)

Choose the correct answer from the options given below:

(A) (A) only (B) (B) only

Give tight bounds for T(n) = 4T(√n) + lg²n, with T(n) constant for n ≤ 2.

The time complexity to multiply two polynomials of degree n using Fast Fourier transform method is :

The following multithreaded algorithm computes transpose of a matrix in parallel : p Trans (X, Y, N) if N = 1 ← then Y[1,1] X[1,1] else partition X into four (N/2) x (N/2) X X X X submatrices 11, 12, 21, 22 partition Y into four (N/2) x (N/2) submatrices Y Y Y Y 11, 12, 21, 22 X Y spawn p Trans ( 11. 11.N/2) X Y spawn p Trans ( 12. 12.N/2) X Y spawn p Trans ( 21. 21.N/2) X Y spawn p Trans ( 22. 22.N/2) What is the asymptotic parallelism of the algorithm?

Consider the following statements :

(a) The running time of dynamic programming θ(ρ) ρ algorithm is alway where is number of subproblems.

(b) When a recurrence relation has cyclic dependency, it is impossible to use that recurrence relation (unmodified) in a correct dynamic program.

(c) For a dynamic programming algorithm, computing all values in a bottom-up fashion is asymptotically faster than using recursion and memorization. X

(d) If a problem can be reduced to a known X NP-hard problem, then must be NP-hard. Which of the statement(s) is (are) true?

Consider the complexity class as the ¯¯¯ L ∈ NP set of languages L such that , and the following two statements :

S : P ⊆ CO − NP 1 S NP ≠ CO − NP P ≠ NP

2 : If , then Which of the following is/are correct? S

The solution of recurrence relation : T(n) = 2T(sqrt(n)) + lg(n) is

The solution of the recurrence relation T(m) = T(3 m/4) + 1 is :