GATE CS question library

Let $r_i(z)$ and $w_i(z)$ denote read and write operations respectively on a data item $z$ by a transaction $T_i$. Consider the following two schedules. $S_1: r_1(x)r_1(y)r_2(x)r_2(y)w_2(y)w_1(x)$ $S_2: r_1(x)r_2(x)r_2(y)w_2(y)r_1(y)w_1(x)$ Which one of the following options is correct?

Let $G$ be a group of order $6$, and $H$ be a subgroup of $G$ such that $1<|H|<6$. Which one of the following options is correct?

Consider the relation $R(P,Q,S,T,X,Y,Z,W)$ with the following functional dependencies. $$PQ\rightarrow X;\quad P\rightarrow YX;\quad Q\rightarrow Y; \quad Y\rightarrow ZW$$ Consider the decomposition of the relation $R$ into the constituent relations according to the following two decomposition schemes. …

Consider the two statements. $S_1:\quad$ There exist random variables $X$ and $Y$ such that $\left(\mathbb E[(X-\mathbb E(X))(Y-\mathbb E(Y))]\right)^2>\textsf{Var}[X]\textsf{Var}[Y]$ $S_2:\quad$ For all random variables $X$ and $Y, \textsf{Cov}[X,Y]=\mathbb E \left[|X-\mathbb E[X]|\;|Y-\mathbb E[Y]|\right ]$ Which one of the following …

Let $G=(V, E)$ be an undirected unweighted connected graph. The diameter of $G$ is defined as: $$\text{diam}(G)=\displaystyle \max_{u,v\in V} \{\text{the length of shortest path between $u$ and $v$}\}$$ Let $M$ be the adjacency matrix of $G$. Define graph $G_2$ on the same set of vertices with adjacency matrix $N$, where …

​​​​​Consider the following$\text{ ANSI C}$ program. #include <stdio.h> int main() { int i, j, count; count=0; i=0; for (j=-3; j<=3; j++) { if (( j >= 0) && (i++)) count = count + j; } count = count +i; printf("%d", count); return 0; } Which one of the following options is correct?

Consider the following language: $$L= \{ w \in \{0,1\}^* \mid w \text{ ends with the substring } 011 \}$$ Which one of the following deterministic finite automata accepts $L?$

For a Turing machine $M$, $\langle M \rangle$ denotes an encoding of $M$. Consider the following two languages. $$\begin{array}{ll} L_1 = \{ \langle M \rangle \mid M \text{ takes more than } 2021 \text{ steps on all inputs} \} \\ L_2 = \{ \langle M \rangle \mid M\text{ takes more than } 2021 \text{ steps on some input} \} \end{array}$$ Which one of the …

Define $R_n$ to be the maximum amount earned by cutting a rod of length $n$ meters into one or more pieces of integer length and selling them. For $i>0$, let $p[i]$ denote the selling price of a rod whose length is $i$ meters. Consider the array of prices: …

An $articulation$ $point$ in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components. Let $T$ be a $\text{DFS}$ tree obtained by doing $\text{DFS}$ in a connected undirected graph $G$. Which of the following options is/are correct?

Consider the following Boolean expression. $F=(X+Y+Z)(\overline X +Y)(\overline Y +Z)$ Which of the following Boolean expressions is/are equivalent to $\overline F$ (complement of $F$)?

A relation $R$ is said to be circular if $a\text{R}b$ and $b\text{R}c$ together imply $c\text{R}a$. Which of the following options is/are correct?

A $\text{TCP}$ server application is programmed to listen on port number $P$ on host $S$. A $\text{TCP}$ client is connected to the $\text{TCP}$ server over the network. Consider that while the $\text{TCP}$ connection was active, the server machine $S$ crashed and rebooted. Assume that the client does not use the $\text{TCP}$ keepalive timer. …

Consider two hosts $P$ and $Q$ connected through a router $R$. The maximum transfer unit $\text{(MTU)}$ value of the link between $P$ and $R$ is $1500$ bytes, and between $R$ and $Q$ is $820$ bytes. A $\text{TCP}$ segment of size $1400$ bytes was transferred from $P$ to $Q$ through $R$, with $\text{IP}$ identification value as …

Consider the following pseudocode, where $\textsf{S}$ is a semaphore initialized to $5$ in line $\#2$ and $\textsf{counter}$ is a shared variable initialized to $0$ in line $\#1$. Assume that the increment operation in line $\#7$ is $\textit{not}$ atomic. 1. int counter = 0; 2. Semaphore S = init(5); 3. void parop(void) 4. { 5. wait(S); 6. …

Consider a $\textit{dynamic}$ hashing approach for $4$-bit integer keys: There is a main hash table of size $4$. The $2$ least significant bits of a key is used to index into the main hash table. Initially, the main hash table entries are empty. Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to …

Consider the following $\text{ANSI C}$ function: int SimpleFunction(int Y[], int n, int x) { int total = Y[0], loopIndex; for (loopIndex=1; loopIndex<=n-1; loopIndex++) total=x*total +Y[loopIndex]; return total; } Let $\textsf{Z}$ be an array of $10$ elements with $\textsf{Z}[i]=1$, for all $i$ such that $0 \leq i \leq 9$. The value returned …

Consider the sliding window flow-control protocol operating between a sender and a receiver over a full-duplex error-free link. Assume the following: The time taken for processing the data frame by the receiver is negligible. The time taken for processing the acknowledgement frame by the sender is negligible. The sender has infinite number of frames …

In a pushdown automaton $P=(Q, \Sigma, \Gamma, \delta, q_0, F)$, a transition of the form, where $p,q \in Q$, $a \in \Sigma \cup \{ \epsilon \}$, and $X,Y \in \Gamma \cup \{ \epsilon \}$, represents $$(q,Y) \in \delta(p,a,X).$$Consider the following pushdown automaton over the input alphabet $\Sigma = \{a,b\}$ and stack alphabet …

Consider the following $C$ code segment: a = b + c; e = a + 1; d = b + c; f = d + 1; g = e + f; In a compiler, this code segment is represented internally as a directed acyclic graph $\text{(DAG)}$. The number of nodes in the $\text{DAG}$ is _____________