Consider an array $A$ of integers of size $n$. The indices of $A$ run from 1 to $n$. An algorithm is to be designed to check whether $A$ satisfies the condition given below.

$\forall i, j \in\{1, \ldots, n-1\}$ such that $i>j,(A[i+1]-A[i])>(A[j+1]-A[j])$

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 $T$, where the elements $T[i][j], 0 \leq i, j \leq n$, 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:

$$ \begin{array}{ll} T[0][k]=T[k][0]=1 & \text { for } k=0,1,2, \ldots, n \\ T[i][j]=2 T[i-1][j]+3 T[i][j-1] & \text { for } 1 \leq i, j \leq n \end{array} $$

Consider the following two algorithms to compute entries of $T$. Assume that for both the algorithms, for all $0 \leq i, j \leq n, T[i][j]$ has been initialized to 1 .

Algorithm $B_k, k \in\{1,2\}$ is said to be correct if and only if it calculates the correct values of $T[i][j]$, for all $0 \leq i, j \leq n$, (as per the recursive formulation) at the end of the execution of the algorithm $B_k$.

Which one of the following statements is true?

A lexical analyzer uses the following token definitions

• letter → [A - Za - z]

• digit → [0-9]

• id → letter (letter $\mid$ digit)*

• number → digit $^{+}$

• ws → (blank | tab | newline) ${ }^{+}$

For the string given below,

$x1 \quad 23mm \quad 78\quad$ y $\quad7 z \quad z z 5 \quad 14 A \quad 8 H \quad A a Y c D$

the number of tokens (excluding ws) that will be produced by the lexical analyzer is

$\_\_\_\_$ . (answer in integer)

Consider the canonical $L R(0)$ parsing of the grammar below using terminals $\{a, b, c\}$ and non-terminals $\{A, B, C, S\}$ with $S$ as the start symbol.

$$ \begin{aligned} & S \rightarrow A C B \\ & A \rightarrow \alpha A \mid \in \\ & C \rightarrow c C \mid \in \\ & B \rightarrow b B \mid b \end{aligned} $$

Which one of the following options gives the number of shift-reduce conflicts that will occur in the $L R(0)$ ACTION table?