GATE CS question library

Consider three IP networks $A, B$ and $C$. Host $H_A$ in network $A$ sends messages each containing $180$ $bytes$ of application data to a host $H_C$ in network $C$. The TCP layer prefixes $20$ byte header to the message. This passes through an intermediate network $B$. The maximum packet size, including $20$ byte IP header, in each …

Consider the grammar rule $E \rightarrow E1 – E2$ for arith­metic expressions. The code generated is targeted to a CPU having a single user register. The sub­traction operation requires the first operand to be in the register. If $E1$ and $E2$ do not have any com­mon sub expression, in order to get the shortest possible code

Choose the best matching between the programming styles in Group 1 and their characteristics in Group 2. …

Consider the following program segment for a hypothetical CPU having three user registers $R_1, R_2$ and $R_3.$ \begin{array}{|l|l|c|} \hline \text {Instruction} & \text{Operation }& \text{Instruction size (in Words)} \\\hline \text{MOV $R_1,5000$} & \text{$R1$} \leftarrow \text{Memory$[5000]$}& \text{$2$} \\\hline\text{MOV …

$L_1$ is a recursively enumerable language over $\Sigma$. An algorithm $A$ effectively enumerates its words as $\omega_1, \omega_2, \omega_3, \dots .$ Define another language $L_2$ over $\Sigma \cup \left\{\text{\#}\right\}$ as $\left\{w_i \text{\#} w_j \mid w_i, w_j \in L_1, i < j \right\}$. Here # is new symbol. Consider the following …

Consider the following grammar G: $S \rightarrow bS \mid aA \mid b$ $A \rightarrow bA \mid aB$ $B \rightarrow bB \mid aS \mid a$ Let $N_a(w)$ and $N_b(w)$ denote the number of a’s and b’s in a string $\omega$ respectively. The language $L(G)$ over $\left\{a, b\right\}^+$ generated by $G$ is

The following finite state machine accepts all those binary strings in which the number of $1$’s and $0$’s are respectively:

The language $\left\{a^mb^nc^{m+n} \mid m, n \geq1\right\}$ is

A program takes as input a balanced binary search tree with $n$ leaf nodes and computes the value of a function $g(x)$ for each node $x$. If the cost of computing $g(x)$ is: $$\Large \min \left ( \substack{\text{number of leaf-nodes}\\\text{in left-subtree of $x$}}\;,\; \substack{\text{number of leaf-nodes}\\\text{in right-subtree of $x$}}\right )$$ …

The recurrence equation $T(1) = 1$ $T(n) = 2T(n-1) + n, n \geq 2$ evaluates to

Let $A[1,\ldots,n]$ be an array storing a bit ($1$ or $0$) at each location, and $f(m)$ is a function whose time complexity is $\Theta(m)$. Consider the following program fragment written in a C like language: counter = 0; for (i=1; i<=n; i++) { if (a[i] == 1) counter++; else {f (counter); counter = 0;} } The complexity of this program fragment …

The time complexity of the following C function is (assume $n > 0$) int recursive (int n) { if(n == 1) return (1); else return (recursive (n-1) + recursive (n-1)); }

Let $G_1=(V,E_1)$ and $G_2 =(V,E_2)$ be connected graphs on the same vertex set $V$ with more than two vertices. If $G_1 \cap G_2= (V,E_1\cap E_2)$ is not a connected graph, then the graph $G_1\cup G_2=(V,E_1\cup E_2)$

A point is randomly selected with uniform probability in the $X-Y$ plane within the rectangle with corners at $(0,0), (1,0), (1,2)$ and $(0,2).$ If $p$ is the length of the position vector of the point, the expected value of $p^{2}$ is

How many graphs on $n$ labeled vertices exist which have at least $\frac{(n^2 - 3n)}{ 2}$ edges ?

Two $n$ bit binary strings, $S_1$ and $S_2$ are chosen randomly with uniform probability. The probability that the Hamming distance between these strings (the number of bit positions where the two strings differ) is equal to $d$ is

The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is

In an $M \times N$ matrix all non-zero entries are covered in $a$ rows and $b$ columns. Then the maximum number of non-zero entries, such that no two are on the same row or column, is

Mala has the colouring book in which each English letter is drawn two times. She wants to paint each of these $52$ prints with one of $k$ colours, such that the colour pairs used to colour any two letters are different. Both prints of a letter can also be coloured with the same colour. What is the minimum value of $k$ that satisfies this requirement?

An examination paper has $150$ multiple choice questions of one mark each, with each question having four choices. Each incorrect answer fetches $-0.25$ marks. Suppose $1000$ students choose all their answers randomly with uniform probability. The sum total of the expected marks obtained by all these students is