All 65 questions of GATE 2017 CS (Set 1)

Research in the workplace reveals that people work for many reasons ________.

Find the smallest number $y$ such that $y \times 162$ is a perfect cube.

Rahul, Murali, Srinivas and Arul are seated around a square table. Rahul is sitting to the left of Murali. Srinivas is sitting to the right of Arul. Which of the following pairs are seated opposite each other?

After Rajendra Chola returned from his voyage to Indonesia, he ________ to visit the temple in Thanjavur.

The probability that a 6-digit number does NOT contain the digits 0, 5, or 9 is:

The expression

is equal to:

Six people are seated around a circular table. There are at least two men and two women. There are at least three right-handed persons. Every woman has a left-handed person to her immediate right. None of the women are right-handed. The number of women at the table is:

“The hold of the nationalist imagination on our colonial past is such that anything inadequately or improperly nationalist is just not history.”

Which of the following statements best reflects the author's opinion?

Arun, Gulab, Neel and Shweta must choose one shirt each from a pile of four shirts coloured red, pink, blue and violet respectively. Arun dislikes the colour red and Shweta dislikes the colour violet. Gulab and Neel like all the colours. In how many different ways can they choose the shirts so that no one has a shirt with a colour he or she dislikes?

A contour line joins locations having the same height above the mean sea level. The following is a contour plot of a geographical region. Contour lines are shown at 25 m intervals in this plot.

If in a flood, the water level rises to 525 m, which of the villages P, Q, R, S, T get submerged?

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

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

Consider the following context-free grammar over the alphabet $\Sigma=\{a,b,c\}$ with $S$ as the start symbol:

Which one of the following represents the language generated by the above grammar?

Consider the C struct defined below:

struct data {
    int marks[100];
    char grade;
    int cnumber;
};

struct data student;

The base address of student is available in register R1. The field student.grade can be accessed efficiently using:

Consider the following functions from positive integers to real numbers:

The correct arrangement of the above functions in increasing order of asymptotic complexity is:

Consider the following table:

Match the algorithms to the design paradigms they are based on.

Let $X$ be a Gaussian random variable with mean 0 and variance $\sigma^2$. Let

where $\max(a,b)$ is the maximum of $a$ and $b$.

The median of $Y$ is __________.

Consider the following intermediate program in three address code:

p = a - b
q = p * c
p = u * v
q = p + q

Which one of the following corresponds to a static single assignment form of the above code?

Consider the Karnaugh map given below, where x represents “don't care” and blank represents 0.

Assume for all inputs $(a,b,c,d)$, the respective complements $(\overline{a},\overline{b},\overline{c},\overline{d})$ are also available. The above logic is implemented using 2-input NOR gates only.

The minimum number of gates required is __________.

Consider a database that has the relation schema EMP(EmpId, EmpName, DeptName). An instance of the schema EMP and a SQL query on it are given below.

SELECT AVG(EC.Num)
FROM EC
WHERE (DeptName, Num) IN
      (SELECT DeptName, COUNT(EmpId) AS EC(DeptName, Num)
       FROM EMP
       GROUP BY DeptName);

The output of executing the SQL query is __________.

Let $T$ be a tree with 10 vertices. The sum of the degrees of all the vertices in $T$ is __________.

The statement $(\neg p) \Rightarrow (\neg q)$ is logically equivalent to which of the statements below?

I. $p \Rightarrow q$

II. $q \Rightarrow p$

III. $(\neg q) \vee p$

IV. $(\neg p) \vee q$

A sender $S$ sends a message $m$ to receiver $R$, which is digitally signed by $S$ with its private key.

In this scenario, one or more of the following security violations can take place.

(I) $S$ can launch a birthday attack to replace $m$ with a fraudulent message.

(II) A third-party attacker can launch birthday attack to replace $m$ with a fraudulent message.

(III) $R$ can launch a birthday attack to replace $m$ with a fraudulent message.

Which of the following are possible security violations?

Threads of a process share:

Consider the language $L$ given by the regular expression

over the alphabet $\{a,b\}$.

The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting $L$ is __________.

The $n$-bit fixed-point representation of an unsigned real number $X$ uses $f$ bits for the fraction part. Let $i=n-f$. The range of decimal values for $X$ in this representation is:

When two 8-bit numbers $A_7\cdots A_0$ and $B_7\cdots B_0$ in 2's complement representation, with $A_0$ and $B_0$ as the least significant bits, are added using a ripple-carry adder, the sum bits obtained are $S_7\cdots S_0$ and the carry bits are $C_7\cdots C_0$.

An overflow is said to have occurred if:

Let $c_1,\ldots,c_n$ be scalars, not all zero, such that

where $a_i$ are column vectors in $\mathbb{R}^n$.

Consider the set of linear equations

where

and

The set of equations has:

Consider the C code fragment given below.

typedef struct node {
    int data;
    node* next;
} node;

void join(node* m, node* n) {
    node* p = n;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = m;
}

Assuming that $m$ and $n$ point to valid NULL-terminated linked lists, invocation of join will:

Consider the following C code:

#include <stdio.h>

int *assignval(int *x, int val) {
    *x = val;
    return x;
}

void main() {
    int *x = malloc(sizeof(int));
    if (NULL == x) return;
    x = assignval(x, 0);
    if (x) {
        x = (int *) malloc(sizeof(int));
        if (NULL == x) return;
        x = assignval(x, 10);
    }
    printf("%d\n", *x);
    free(x);
}

The code suffers from which one of the following problems?

Consider the first-order logic sentence

Assuming non-empty logical domains, which of the sentences below are implied by $F$?

I. $\exists y(\exists xR(x,y))$

II. $\exists y(\forall xR(x,y))$

III. $\forall y(\exists xR(x,y))$

IV. $\neg\exists x(\forall y\neg R(x,y))$

Consider the following CPU processes with arrival times and length of CPU bursts 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.

Consider the following grammar:

What is FOLLOW$(Q)$?

Let $T$ be a binary search tree with 15 nodes. The minimum and maximum possible heights of $T$ are:

Note: The height of a tree with a single node is 0.

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 __________.

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. Server-side TCP responds by sending an ACK, which is received by the client-side TCP.

As per the TCP connection state diagram, in which state does the client-side TCP connection wait for the FIN from the server-side TCP?

Consider the context-free grammars over the alphabet $\{a,b,c\}$ given below. $S$ and $T$ are non-terminals.

The language $L(G_1)\cap L(G_2)$ is:

The value of

A computer network uses polynomials over $GF(2)$ for error checking with 8 bits as information bits and uses

as the generator polynomial to generate the check bits.

In this network, the message 01011011 is transmitted as:

Let $u$ and $v$ be two vectors in $\mathbb{R}^2$ whose Euclidean norms satisfy

What is the value of $\alpha$ such that

bisects the angle between $u$ and $v$?

Consider the C functions foo and bar given below:

int foo(int val) {
    int x = 0;
    while (val > 0) {
        x = x + foo(val--);
    }
    return val;
}

int bar(int val) {
    int x = 0;
    while (val > 0) {
        x = x + bar(val - 1);
    }
    return val;
}

Invocations of foo(3) and bar(3) will result in:

Consider a database that has the relation schemas EMP(EmpId, EmpName, DeptId), and DEPT(DeptName, DeptId). Note that DeptId can be permitted to be NULL in the relation EMP.

Consider the following queries on the database expressed in tuple relational calculus.

I. $\{t\mid \exists u\in EMP(t[EmpName]=u[EmpName]\wedge \forall v\in DEPT(t[DeptId]\ne v[DeptId]))\}$

II. $\{t\mid \exists u\in EMP(t[EmpName]=u[EmpName])\wedge \exists v\in DEPT(t[DeptId]=v[DeptId])\}$

III. $\{t\mid \exists u\in EMP(t[EmpName]=u[EmpName])\wedge \exists v\in DEPT(t[DeptId]\ne v[DeptId])\}$

Which of the above queries are safe?

A multithreaded program $P$ executes with $x$ number of threads and uses $y$ number of locks for ensuring mutual exclusion while operating on shared memory locations. All locks in the program are non-reentrant, i.e., if a thread holds a lock $l$, then it cannot re-acquire lock $l$ without releasing it. If a thread is unable to acquire a lock, it blocks until the lock becomes available.

The minimum value of $x$ and the minimum value of $y$ together for which execution of $P$ can result in a deadlock are:

Let $p$, $q$, and $r$ be propositions and the expression $(p\to q)\to r$ be a contradiction. Then, the expression $(r\to p)\to q$ is:

If $G$ is a grammar with productions

where $S$ is the start variable, then which one of the following strings is not generated by $G$?

In a database system, unique timestamps are assigned to each transaction using Lamport's logical clock. Let $TS(T_1)$ and $TS(T_2)$ be the timestamps of transactions $T_1$ and $T_2$ respectively.

$T_1$ holds a lock on the resource $R$, and $T_2$ has requested a conflicting lock on the same resource $R$.

The following algorithm is used to prevent deadlocks in the database system assuming that a killed transaction is restarted with the same timestamp.

if TS(T2) < TS(T1) then
    T1 is killed
else
    T2 waits

Assume any transaction that is not killed terminates eventually.

Which of the following is TRUE about the database system that uses the above algorithm to prevent deadlocks?

Consider the following two functions.

void fun1(int n) {
    if (n == 0) return;
    printf("%d", n);
    fun2(n - 2);
    printf("%d", n);
}

void fun2(int n) {
    if (n == 0) return;
    printf("%d", n);
    fun1(++n);
    printf("%d", n);
}

The output printed when fun1(5) is called is:

Consider a combination of T and D flip-flops connected as shown below. The output of the D flip-flop is connected to the input of the T flip-flop and the output of the T flip-flop is connected to the input of the D flip-flop.

Initially, both $Q_0$ and $Q_1$ are set to 1 before the 1st clock cycle. The outputs are:

Recall that Belady's anomaly is that the page-fault rate may increase as the number of allocated frames increases. Now, consider the following statements:

S1: Random page replacement algorithm, where a page chosen at random is replaced, suffers from Belady's anomaly.

S2: LRU page replacement algorithm suffers from Belady's anomaly.

Which of the following is CORRECT?

Let $A$ and $B$ be finite alphabets and let # be a symbol outside both $A$ and $B$. Let $f$ be a total function from $A^*$ to $B^*$. We say $f$ is computable if there exists a Turing machine $M$ which, given an input $x$ in $A^*$, always halts with $f(x)$ on its tape.

Let $L_f$ denote the language

Which of the following statements is true?

Let $A$ be an $n\times n$ real-valued square symmetric matrix of rank 2 with

Consider the following statements.

I. One eigenvalue must be in $[-5,5]$

II. The eigenvalue with the largest magnitude must be strictly greater than 5

Which of the above statements about eigenvalues of $A$ is/are necessarily CORRECT?

Consider the following languages over the alphabet $\Sigma=\{a,b,c\}$.

and

Which of the following are context-free languages?

I. $L_1\cup L_2$

II. $L_1\cap L_2$

Let $G=(V,E)$ be any connected undirected edge-weighted graph. The weights of the edges in $E$ are positive and distinct. Consider the following statements:

I. Minimum Spanning Tree of $G$ is always unique.

II. Shortest path between any two vertices of $G$ is always unique.

Which of the above statements is/are necessarily true?

Consider a database table COURSES_REGISTERED with schema:

CR(StudentName, CourseName)

The instance of CR is given below:

Consider the following relational algebra query:

The number of rows in $T2$ is __________.

Consider the following grammar:

stmt   -> if expr then expr else expr; stmt | ε
expr   -> term relop term | term
term   -> id | number
id     -> a | b | c
number -> [0-9]

where relop is a relational operator, for example <, >, and so on, ε refers to the empty statement, and if, then, else are terminals.

Consider a program $P$ following the above grammar containing ten if terminals. The number of control flow paths in $P$ is __________.

For example, the program

if e1 then e2 else e3

has 2 control flow paths:

e1 -> e2
e1 -> e3

In an RSA cryptosystem, a participant $A$ uses two prime numbers

and

to generate her public and private keys. If the public key of $A$ is 35, then the private key of $A$ is __________.

Consider the following C program:

#include <stdio.h>
#include <string.h>

void printlength(char *s, char *t) {
    unsigned int c = 0;
    int len = ((strlen(s) - strlen(t)) > c) ? strlen(s) : strlen(t);
    printf("%d\n", len);
}

void main() {
    char *x = "abc";
    char *y = "defgh";
    printlength(x, y);
}

Recall that strlen is defined in string.h as returning a value of type size_t, which is an unsigned integer type.

The output of the program is __________.

Instruction execution in a processor is divided into 5 stages:

1. Instruction Fetch (IF)
2. Instruction Decode (ID)
3. Operand Fetch (OF)
4. Execute (EX)
5. Write Back (WB)

These stages take 5 ns, 4 ns, 20 ns, 10 ns, and 3 ns respectively.

A pipelined implementation of the processor requires buffering between each pair of consecutive stages with a delay of 2 ns.

Two pipelined implementations of the processor are contemplated:

1. A naive pipeline implementation (NP) with 5 stages.
2. An efficient pipeline implementation (EP), where the OF stage is divided into stages OF1 and OF2 with execution times of 12 ns and 8 ns respectively.

The speedup, correct to two decimal places, achieved by EP over NP in executing 20 independent instructions with no hazards is __________.

Consider a RISC machine where each instruction is exactly 4 bytes long. Conditional and unconditional branch instructions use PC-relative addressing mode with Offset specified in bytes to the target location of the branch instruction.

Further, the Offset is always with respect to the address of the next instruction in the program sequence.

Consider the following instruction sequence:

i:     add R2, R3, R4
i+1:   sub R5, R6, R7
i+2:   cmp R1, R9, R10
i+3:   beq R1, Offset

If the target of the branch instruction is instruction $i$, then the decimal value of Offset is __________.

The values of parameters for the Stop-and-Wait ARQ protocol are as given below:

Assume that there are no transmission errors.

The transmission efficiency, expressed in percentage and correct to 2 decimal places, of the Stop-and-Wait ARQ protocol for the above parameters is __________.

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

The output of executing the following C program is __________.

#include <stdio.h>

int total(int v) {
    static int count = 0;
    while (v) {
        count += v & 1;
        v >>= 1;
    }
    return count;
}

void main() {
    static int x = 0;
    int i = 5;
    for (; i > 0; i--) {
        x = x + total(i);
    }
    printf("%d\n", x);
}

A cache memory unit with capacity of $N$ words and block size of $B$ words is to be designed.

If it is designed as a direct-mapped cache, the length of the TAG field is 10 bits.

If the cache unit is now designed as a 16-way set-associative cache, the length of the TAG field is __________ bits.

Let $A$ be an array of 31 numbers consisting of a sequence of 0's followed by a sequence of 1's.

The problem is to find the smallest index $i$ such that $A[i]$ is 1 by probing the minimum number of locations in $A$.

The worst-case number of probes performed by an optimal algorithm is __________.

Consider the expression:

Let $X$ be the minimum number of registers required by an optimal code generation algorithm, without any register spill, for a load/store architecture in which:

1. only load and store instructions can have memory operands, and
2. arithmetic instructions can have only register or immediate operands.

The value of $X$ is __________.

Consider a 2-way set associative cache with 256 blocks and LRU replacement. Initially the cache is empty.

Conflict misses are those misses which occur due to contention of multiple blocks for the same cache set. Compulsory misses occur due to first-time access to the block.

The following sequence of accesses to memory blocks:

(0, 128, 256, 128, 0, 128, 256, 128, 1, 129, 257, 129, 1, 129, 257, 129)

is repeated 10 times.

The number of conflict misses experienced by the cache is __________.