GATE CS question library

Three processes arrive at time zero with $\text{CPU}$ bursts of $16,\;20$ and $10$ milliseconds. If the scheduler has prior knowledge about the length of the $\text{CPU}$ bursts, the minimum achievable average waiting time for these three processes in a non-preemptive scheduler (rounded to nearest integer) is _____________ milliseconds.

​​​Consider the following grammar (that admits a series of declarations, followed by expressions) and the associated syntax directed translation $\text{(SDT)}$ actions, given as pseudo-code …

The following relation records the age of $500$ employees of a company, where $empNo$ (indicating the employee number) is the key: $$empAge(\underline{empNo},age)$$ Consider the following relational algebra expression: $$\Pi_{empNo}(empAge \Join_{(age>age1)} \rho_{empNo1,age1}(empAge))$$ What does the above expression generate?

Consider a $3$-bit counter, designed using $T$ flip-flops, as shown below: Assuming the initial state of the counter given by $\text{PQR}$ as $000$, what are the next three states?

Assume that a $12$-bit Hamming codeword consisting of $8$-bit data and $4$ check bits is $d_8d_7d_6d_5c_8d_4d_ 4d_3d_2c_4d_1c_2c_1$, where the data bits and the check bits are given in the following tables: …

Consider the following context-free grammar where the set of terminals is $\{a,b,c,d,f\}$. …

Consider the following recurrence relation. $$T\left ( n \right )=\left\{\begin{array} {lcl} T(n ∕ 2)+T(2n∕5)+7n & \text{if} \; n>0\\1 & \text{if}\; n=0 \end{array}\right.$$ Which one of the following options is correct?

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