GATE CS question library

The set $\{1, 2, 4, 7, 8, 11, 13, 14\}$ is a group under multiplication modulo $15$. The inverses of $4$ and $7$ are respectively:

Let $G$ be a simple graph with $20$ vertices and $100$ edges. The size of the minimum vertex cover of G is $8$. Then, the size of the maximum independent set of $G$ is:

Let $f(x)$ be the continuous probability density function of a random variable $x$, the probability that $a < x \leq b$, is :

Let $G$ be a simple connected planar graph with $13$ vertices and $19$ edges. Then, the number of faces in the planar embedding of the graph is:

Let $A, B$ and $C$ be non-empty sets and let $X = ( A - B ) - C$ and $Y = ( A - C ) - ( B - C ).$ Which one of the following is TRUE?

The following is the Hasse diagram of the poset $\left[\{a,b,c,d,e\},≺\right]$ The poset is :

Suppose there are $\lceil \log n \rceil$ sorted lists of $\lfloor n /\log n \rfloor$ elements each. The time complexity of producing a sorted list of all these elements is: (Hint:Use a heap data structure)

Consider the following circuit involving a positive edge triggered D FF. Consider the following timing diagram. Let $A_{i}$ represents the logic level on the line $A$ in the $i$-th clock period. Let $A'$ represent the complement of $A$. The correct output sequence on $Y$ over the clock periods $1$ through $5$ is:

Consider the following code fragment: if (fork() == 0) { a = a + 5; printf("%d, %p n", a, &a); } else { a = a - 5; printf ("%d, %p n", a,& a); } Let $u,v$ be the values printed by the parent process and $x,y$ be the values printed by the child process. Which one of the following is TRUE?

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 …