GATE CS 2017 — Previous Year Questions

A message is made up entirely of characters from the set \(X = \{P, Q, R, S, T\}\). The table of probabilities for each of the characters is shown below.

If a message of 100 characters over \(X\) is encoded using Huffman coding, then the expected length of the encoded message in bits is ______.

Consider the following grammar:

P → x Q R S
Q → y z | z
R → w | ε
S → y

What is FOLLOW(Q)?

Consider a TCP client and a TCP server running on two different machines. After completing data transfer, the TCP client calls close to terminate the connection and a FIN segment is sent to the TCP server. The server-side TCP responds by sending an ACK, which is received by the client-side TCP. As per the TCP connection state diagram (RFC 793), in which state does the client-side TCP connection wait for the FIN from the server-side TCP?

Consider a two-level cache hierarchy with L1 and L2 caches. An application incurs 1.4 memory accesses per instruction on average. For this application, the miss rate of L1 cache is 0.1; the L2 cache experiences, on average, 7 misses per 1000 instructions. The miss rate of L2 expressed correct to two decimal places is ______.

The following functional dependencies hold true for the relational schema \(R\{V, W, X, Y, Z\}\):

V  -> W
VW -> X
Y  -> VX
Y  -> Z

Which of the following is irreducible equivalent for this set of functional dependencies?

Consider the Boolean operator \(\#\) with the following properties:

\(x \# 0 = x\),   \(x \# 1 = \overline{x}\),   \(x \# x = 0\)   and   \(x \# \overline{x} = 1\).

Then \(x \# y\) is equivalent to:

The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is ______.

If \(f(x) = R\sin\left(\dfrac{\pi x}{2}\right) + S\), \(f'\left(\dfrac{1}{2}\right) = \sqrt{2}\) and \(\displaystyle\int_{0}^{1} f(x)\,dx = \dfrac{2R}{\pi}\), then the constants \(R\) and \(S\) are respectively

If the characteristic polynomial of a \(3\times 3\) matrix \(M\) over \(\mathbb{R}\) (the set of real numbers) is \(\lambda^{3} - 4\lambda^{2} + a\lambda + 30\), \(a \in \mathbb{R}\), and one eigenvalue of \(M\) is \(2\), then the largest among the absolute values of the eigenvalues of \(M\) is ______.

The ninth and the tenth of this month are Monday and Tuesday ________.

Choose the word that best fills the blank.

A jar contains a mixture of 175 ml water and 700 ml alcohol. Gopal takes out 10% of the mixture and substitutes it by water of the same amount. The process is repeated once again.

The percentage of water in the mixture is ________.

Consider the following CPU processes with arrival times (in milliseconds) and length of CPU bursts (in milliseconds) as given below:

If the pre-emptive shortest remaining time first scheduling algorithm is used to schedule the processes, then the average waiting time across all processes is _______ milliseconds.

\(P\) and \(Q\) are considering to apply for a job. The probability that \(P\) applies for the job is \(\dfrac{1}{4}\), the probability that \(P\) applies for the job given that \(Q\) applies for the job is \(\dfrac{1}{2}\), and the probability that \(Q\) applies for the job given that \(P\) applies for the job is \(\dfrac{1}{3}\). Then the probability that \(P\) does not apply for the job given that \(Q\) does not apply for the job is

Consider the following C program:

#include <stdio.h>

int *A, stkTop;

int stkFunc(int opcode, int val) {
    static int size = 0, stkTop = 0;
    switch (opcode) {
        case -1: size = val; break;
        case  0: if (stkTop < size) A[stkTop++] = val; break;
        default: if (stkTop) return A[--stkTop];
    }
    return -1;
}

int main() {
    int B[20];
    A = B;
    stkTop = -1;
    stkFunc(-1, 10);
    stkFunc(0, 5);
    stkFunc(0, 10);
    printf("%d\n", stkFunc(1, 0) + stkFunc(1, 0));
    return 0;
}

The value printed by the program is ______.

Consider the language \(L\) given by the regular expression \((a+b)^*b(a+b)\) over the alphabet \(\{a,b\}\). The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting \(L\) is ______.