Consider an array $A=[10,7,8,19,41,35,25,31]$. Suppose the merge sort algorithm is executed on array $A$ to sort it in increasing order. The merge sort algorithm will carry out a total of 7 merge operations.

A merge operation on sorted left array $L$ and sorted right array $R$ is said to be void if the output of the merge operation is the elements of array $L$ followed by the elements of array $R$.

The number of void merge operations among these 7 merge operations is $\_\_\_\_$ . (answer in integer)

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)