GATE CS question library

Consider a simple communication system where multiple nodes are connected by a shared broadcast medium (like Ethernet or wireless). The nodes in the system use the following carrier-sense based medium access protocol. A node that receives a packet to transmit will carrier-sense the medium for $5$ units of time. If the node does not detect any other …

Consider a storage disk with $4$ platters (numbered as $0, 1, 2$ and $3$), $200$ cylinders (numbered as $0, 1, … , 199$), and $256$ sectors per track (numbered as $0, 1, … 255$). The following $6$ disk requests of the form [sector number, cylinder number, platter number] are received by the disk controller at the same time: …

Consider an IP packet with a length of $4,500\;\text{bytes}$ that includes a $20\text{-byte}\;\textsf{IPv4}$ header and a $40\text{-byte}$ TCP header. The packet is forwarded to an $\textsf{IPv4}$ router that supports a Maximum Transmission Unit (MTU) of $600\;\text{bytes}$. Assume that the length of the IP header in all the outgoing fragments of …

Given a language $L$, define $L^i$ as follows:$$L^0 = \{ \varepsilon \}$$$$L^i = L^{i-1} \bullet L \text{ for all } I >0$$The order of a language $L$ is defined as the smallest $k$ such that $L^k = L^{k+1}$. Consider the language $L_1 ($over alphabet $0)$ accepted by the following automaton. The order of $L_1$ is ________.

A processor has $16$ integer registers $\text{(R0, R1}, \ldots ,\text{ R15)}$ and $64$ floating point registers $\text{(F0, F1}, \ldots , \text{F63)}.$ It uses a $2\text{- byte}$ instruction format. There are four categories of instructions: $\text{Type-1, Type-2, Type-3},$ and $\text{Type-4. Type-1}$ category consists of four instructions, …

Consider the minterm list form of a Boolean function $F$ given below. $$F(P, Q, R, S) = \Sigma m(0, 2, 5, 7, 9, 11) + d(3, 8, 10, 12, 14)$$ Here, $m$ denotes a minterm and $d$ denotes a don't care term. The number of essential prime implicants of the function $F$ is ___

The instruction pipeline of a RISC processor has the following stages: Instruction Fetch $(IF)$, Instruction Decode $(ID)$, Operand Fetch $(OF)$, Perform Operation $(PO)$ and Writeback $(WB)$, The $IF$, $ID$, $OF$ and $WB$ stages take $1$ clock cycle each for every instruction. Consider a sequence of $100$ instructions. In the $PO$ …

Consider the weights and values of items listed below. Note that there is only one unit of each item. …

Consider the following undirected graph $G$: Choose a value for $x$ that will maximize the number of minimum weight spanning trees (MWSTs) of $G$. The number of MWSTs of $G$ for this value of $x$ is ____.

The number of possible min-heaps containing each value from $\{1,2,3,4,5,6,7\}$ exactly once is _______

Consider the following program written in pseudo-code. Assume that $x$ and $y$ are integers. Count (x, y) { if (y !=1 ) { if (x !=1) { print("*"); Count (x/2, y); } else { y=y-1; Count (1024, y); } } } The number of times that the $print$ statement is executed by the call $Count(1024, 1024)$ is _____

Consider Guwahati, $(G)$ and Delhi $(D)$ whose temperatures can be classified as high $(H)$, medium $(M)$ and low $(L)$. Let $P(H_G)$ denote the probability that Guwahati has high temperature. Similarly, $P(M_G)$ and $P(L_G)$ denotes the probability of Guwahati having medium and low temperatures respectively. Similarly, we use …

Let $G$ be a graph with $100!$ vertices, with each vertex labelled by a distinct permutation of the numbers $1, 2,\ldots, 100.$ There is an edge between vertices $u$ and $v$ if and only if the label of $u$ can be obtained by swapping two adjacent numbers in the label of $v$. Let $y$ denote the degree of a vertex in $G$, and $z$ denote the …

In a system, there are three types of resources: $E, F$ and $G$. Four processes $P_0$, $P_1$, $P_2$ and $P_3$ execute concurrently. At the outset, the processes have declared their maximum resource requirements using a matrix named Max as given below. For example, Max[$P_2, F$] is the maximum number of instances of $F$ that $P_2$ would …

Consider the following four relational schemas. For each schema , all non-trivial functional dependencies are listed, The bolded attributes are the respective primary keys. $\text{Schema I:}$ Registration(rollno, courses) Field ‘courses’ is a set-valued attribute containing the set of courses a student has registered for. Non-trivial functional dependency …

Consider the relations $r(A, B)$ and $s(B, C)$, where $s.B$ is a primary key and $r.B$ is a foreign key referencing $s.B$. Consider the query $Q: r \bowtie (\sigma_{B<5} (s))$ Let LOJ denote the natural left outer-join operation. Assume that $r$ and $s$ contain no null values. Which of the following is NOT equivalent to $Q$?

The size of the physical address space of a processor is $2^P$ bytes. The word length is $2^W$ bytes. The capacity of cache memory is $2^N$ bytes. The size of each cache block is $2^M$ words. For a $K$-way set-associative cache memory, the length (in number of bits) of the tag field is

A lexical analyzer uses the following patterns to recognize three tokens $T_1, T_2$, and $T_3$ over the alphabet $\{a, b, c\}$. $T_1: a?(b \mid c)^\ast a$ $T_2: b?(a \mid c)^\ast b$ $T_3: c?(b \mid a)^\ast c$ Note that ‘$x?$’ means $0$ or $1$ occurrence of the symbol $x.$ Note also that the analyzer outputs the token that matches the …

Consider the following problems. $L(G)$ denotes the language generated by a grammar $G$. L(M) denotes the language accepted by a machine $M$. For an unrestricted grammar $G$ and a string $w$, whether $w \in L(G)$ Given a Turing machine $M$, whether $L(M)$ is regular Given two grammar$G_1$ and $G_2$, whether $L(G_1) = L(G_2)$ Given an …

Consider the following languages: $\{a^mb^nc^pd^q \mid m+p=n+q, \text{ where } m, n, p, q \geq 0 \}$ $\{a^mb^nc^pd^q \mid m=n \text{ and }p=q, \text{ where } m, n, p, q \geq 0 \}$ $\{a^mb^nc^pd^q \mid m=n =p \text{ and } p \neq q, \text{ where } m, n, p, q \geq 0 \}$ $\{a^mb^nc^pd^q \mid mn =p+q, \text{ where } m, n, p, q \geq 0 \}$ Which of the …