GATE CS question library

Consider a new instruction named branch-on-bit-set (mnemonic bbs). The instruction “bbs reg, pos, label” jumps to label if bit in position pos of register operand reg is one. A register is $32$ -bits wide and the bits are numbered $0$ to $31,$ bit in position $0$ being the least significant. Consider the following emulation of this instruction on a …

A CPU has a five-stage pipeline and runs at $1$ GHz frequency. Instruction fetch happens in the first stage of the pipeline. A conditional branch instruction computes the target address and evaluates the condition in the third stage of the pipeline. The processor stops fetching new instructions following a conditional branch until the branch outcome is …

A CPU has a cache with block size $64$ bytes. The main memory has $k$ banks, each bank being $c$ bytes wide. Consecutive $c$ − byte chunks are mapped on consecutive banks with wrap-around. All the $k$ banks can be accessed in parallel, but two accesses to the same bank must be serialized. A cache block access may involve multiple iterations of …

Consider numbers represented in 4-bit Gray code. Let $h_{3}h_{2}h_{1}h_{0}$ be the Gray code representation of a number $n$ and let $g_{3}g_{2}g_{1}g_{0}$ be the Gray code of $(n+1)(modulo 16)$ value of the number. Which one of the following functions is correct?

We consider the addition of two $2's$ complement numbers $b_{n-1}b_{n-2}\dots b_{0}$ and $a_{n-1}a_{n-2}\dots a_{0}$. A binary adder for adding unsigned binary numbers is used to add the two numbers. The sum is denoted by $c_{n-1}c_{n-2}\dots c_{0}$ and the carry-out by $c_{out}$. Which one of the following options correctly identifies the overflow …

Consider a Boolean function $f(w,x,y,z)$. Suppose that exactly one of its inputs is allowed to change at a time. If the function happens to be true for two input vectors $i_{1}=\left \langle w_{1}, x_{1}, y_{1},z_{1}\right \rangle$ and $i_{2}=\left \langle w_{2}, x_{2}, y_{2},z_{2}\right \rangle$ , we would like the function to remain true as the input …

Consider the circuit in the diagram. The $\oplus$ operator represents Ex-OR. The D flip-flops are initialized to zeroes (cleared). The following data: $100110000$ is supplied to the “data” terminal in nine clock cycles. After that the values of $q_{2}q_{1}q_{0}$ are:

Given two three bit numbers $a_{2}a_{1}a_{0}$ and $b_{2}b_{1}b_{0}$ and $c$ the carry in, the function that represents the carry generate function when these two numbers are added is:

Consider the circuit above. Which one of the following options correctly represents $f\left(x,y,z\right)$

Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is:

Let $L_1$ be a regular language, $L_2$ be a deterministic context-free language and $L_3$ a recursively enumerable, but not recursive, language. Which one of the following statements is false?

Consider the following statements about the context free grammar $$G = \left \{ S \rightarrow SS, S \rightarrow ab, S \rightarrow ba, S \rightarrow \epsilon \right \}$$ $G$ is ambiguous $G$ produces all strings with equal number of $a$’s and $b$’s $G$ can be accepted by a deterministic PDA. Which combination below expresses all the true statements …

Let SHAM$_3$ be the problem of finding a Hamiltonian cycle in a graph $G=(V,E)$ with $|V|$ divisible by $3$ and DHAM$_3$ be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

For $s\in (0+1)^{*}$ let $d(s)$ denote the decimal value of $s ($e.g. $d (101) = 5 ).$ Let $$L=\left \{ s\in (0+1)^*\mid d(s) \text{ mod } 5=2 \text{ and }d(s) \text{ mod } 7\neq 4 \right \}$$Which one of the following statements is true?

If $s$ is a string over $(0+1)^*$ then let $n_0(s)$ denote the number of $0$’s in $s$ and $n_1(s)$ the number of $1$’s in $s$. Which one of the following languages is not regular?

A logical binary relation $\odot$, is defined as follows: …

Consider the following propositional statements: $P_1: ((A ∧ B) → C)) ≡ ((A → C) ∧ (B → C))$ $P_2: ((A ∨ B) → C)) ≡ ((A → C) ∨ (B → C))$ Which one of the following is true?

Which one of the first order predicate calculus statements given below correctly expresses the following English statement? Tigers and lions attack if they are hungry or threatened.

Let $S = \{1, 2, 3,\ldots, m\}, m >3.$ Let $X_1,\ldots,X_n$ be subsets of $S$ each of size $3.$ Define a function $f$ from $S$ to the set of natural numbers as, $f(i)$ is the number of sets $X_j$ that contain the element $i.$ That is $f(i)=\left | \left\{j \mid i\in X_j \right\} \right|$ then $\sum_{i=1}^{m} f(i)$ is:

Given a set of elements $N = {1, 2, ..., n}$ and two arbitrary subsets $A⊆N$ and $B⊆N$, how many of the n! permutations $\pi$ from $N$ to $N$ satisfy $\min(\pi(A)) = \min(\pi(B))$, where $\min(S)$ is the smallest integer in the set of integers $S$, and $\pi$(S) is the set of integers obtained by applying permutation $\pi$ to each …