GATE CS 2019 — Previous Year Questions

There are \(n\) unsorted arrays: \(A_1, A_2, \ldots, A_n\). Assume that \(n\) is odd. Each of \(A_1, A_2, \ldots, A_n\) contains \(n\) distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of \(A_1, A_2, \ldots, A_n\) is

Consider the grammar given below:

S → a S B | d
B → b

The number of reduction steps taken by a bottom-up parser while accepting the string aaadbbb is ______.

Consider three machines \(M\), \(N\) and \(P\) with IP addresses 100.10.5.2, 100.10.5.5 and 100.10.5.6 respectively. The subnet mask is set to 255.255.255.252 for all the three machines. Which one of the following is true?

Consider that 15 machines need to be connected in a LAN using 8-port Ethernet switches. Assume that these switches do not have any separate uplink ports. The minimum number of switches needed is ________.

A certain processor uses a fully associative cache of size 16 kB. The cache block size is 16 bytes. Assume that the main memory is byte addressable and uses a 32-bit address. How many bits are required for Tag and Index fields respectively in the addresses generated by the processor?

Consider the following two statements about database transaction schedules:

I. Strict two-phase locking protocol generates conflict serializable schedules that are also recoverable.

II. Timestamp-ordering concurrency control protocol with Thomas' Write Rule can generate view serializable schedules that are not conflict serializable.

Which of the above statements is/are TRUE?

Consider \(Z = X - Y\), where \(X\), \(Y\) and \(Z\) are all in sign-magnitude form. \(X\) and \(Y\) are each represented in \(n\) bits. To avoid overflow, the representation of \(Z\) would require a minimum of:

Let \(X\) be a square matrix. Consider the following two statements on \(X\).

I. \(X\) is invertible.
II. Determinant of \(X\) is non-zero.

Which one of the following is TRUE?

The strategies that the company ________ to sell its products ________ house-to-house marketing.

Choose the correct option to fill in the blanks.

Suppose \(Y\) is distributed uniformly in the open interval \((1,6)\). The probability that the polynomial \(3x^{2}+6xY+3Y+6\) has only real roots is (rounded off to 1 decimal place) ______.

Consider the following C program:

#include <stdio.h>

int jumble(int x, int y) {
    x = 2 * x + y;
    return x;
}

int main() {
    int x = 2, y = 5;
    y = jumble(y, x);
    x = jumble(y, x);
    printf("%d\n", x);
    return 0;
}

The value printed by the program is ______.

For \(\Sigma = \{a,b\}\), let us consider the regular language \(L = \{x \mid x = a^{2+3k}\) or \(x = b^{10+12k},\ k \ge 0\}\). Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for \(L\)?