List of top Computer Science and IT Engineering Questions on Algorithm design techniques asked in GATE CS

Consider an array 𝐴 of integers of size 𝑛. The indices of 𝐴 run from 1 to 𝑛. An
algorithm is to be designed to check whether 𝐴 satisfies the condition given below.
∀𝑖, 𝑗∈{1, … , 𝑛−1} such that 𝑖> 𝑗, (𝐴[𝑖+ 1] −𝐴[𝑖]) > (𝐴[𝑗+ 1] −𝐴[𝑗])
Which one of the following gives the worst case time complexity of the fastest
algorithm that can be designed for the problem?

Consider a table 𝑇, where the elements 𝑇[𝑖][𝑗], 0 ≤𝑖, 𝑗≤𝑛, represent the cost of
the optimal solutions of different subproblems of a problem that is being solved
using a dynamic programming algorithm. The recursive formulation to compute the
table entries is as follows:
𝑇[0][𝑘] = 𝑇[𝑘][0] = 1 for 𝑘= 0,1,2, … , 𝑛
𝑇[𝑖][𝑗] = 2𝑇[𝑖−1][𝑗] + 3𝑇[𝑖][𝑗−1] for 1 ≤𝑖, 𝑗≤𝑛
Consider the following two algorithms to compute entries of 𝑇. Assume that for
both the algorithms, for all 0 ≤𝑖, 𝑗≤𝑛, 𝑇[𝑖][𝑗] has been initialized to 1.

Algorithm B1:
For i = 1, 2, ..., n
  For j = 1, 2, ..., n
    T[i][j] = 2T[i-1][j] + 3T[i][j-1]

Algorithm B2:
For s = 2, 3, ..., 2n
  For i = 1, 2, ..., n
    For j = 1, 2, ..., n
      If (i + j == s)
        T[i][j] = 2T[i-1][j] + 3T[i][j-1]

Algorithm 𝐵𝑘, 𝑘∈{1,2} is said to be correct if and only if it calculates the correct
values of 𝑇[𝑖][𝑗], for all 0 ≤𝑖, 𝑗≤𝑛, (as per the recursive formulation) at the end
of the execution of the algorithm 𝐵𝑘.
Which one of the following statements is true?