GATE CS question library

The literal count of a Boolean expression is the sum of the number of times each literal appears in the expression. For example, the literal count of $\left(xy+xz'\right)$ is $4.$ What are the minimum possible literal counts of the product-of-sum and sum-of-product representations respectively of the function given by the following Karnaugh map? Here, …

A $\text{1-input}$, $\text{2-output}$ synchronous sequential circuit behaves as follows: Let $z_k, n_k$ denote the number of $0’s$ and $1’s$ respectively in initial $k$ bits of the input $(z_k+n_k=k)$. The circuit outputs $00$ until one of the following conditions holds. $z_k-n_k=2$. In this case, the output at the k-th and all subsequent …

The following is a scheme for floating point number representation using $16$ bits. Let $s, e,$ and $m$ be the numbers represented in binary in the sign, exponent, and mantissa fields respectively. Then the floating point number represented is: …

Consider the following system of linear equations $$\left( \begin{array}{ccc} 2 & 1 & -4 \\ 4 & 3 & -12 \\ 1 & 2 & -8 \end{array} \right) \left( \begin{array}{ccc} x \\ y \\ z \end{array} \right) = \left( \begin{array}{ccc} \alpha \\ 5 \\ 7 \end{array} \right)$$ Notice that the second and the third columns of the coefficient matrix …

A graph $G=(V,E)$ satisfies $\mid E \mid \leq 3 \mid V \mid - 6$. The min-degree of $G$ is defined as $\min_{v\in V}\left\{ \text{degree }(v)\right \}$. Therefore, min-degree of $G$ cannot be

Let $\Sigma = \left\{a, b, c, d, e\right\}$ be an alphabet. We define an encoding scheme as follows: $g(a) = 3, g(b) = 5, g(c) = 7, g(d) = 9, g(e) = 11$. Let $p_i$ denote the i-th prime number $\left(p_1 = 2\right)$. For a non-empty string $s=a_1 \dots a_n$, where each $a_i \in \Sigma$, define $f(s)= \Pi^n_{i=1}P_i^{g(a_i)}$. For a non-empty …

Let $f : A \to B$ be an injective (one-to-one) function. Define $g : 2^A \to 2^B$ as: $g(C) = \left \{f(x) \mid x \in C\right\}$, for all subsets $C$ of $A$. Define $h : 2^B \to 2^A$ as: $h(D) = \{x \mid x \in A, f(x) \in D\}$, for all subsets $D$ of $B$. Which of the following statements is always true?

Consider the set $\{a, b, c\}$ with binary operators $+$ and $*$ defined as follows: …

How many perfect matching are there in a complete graph of $6$ vertices?

Consider the following recurrence relation $T(1)=1$ $T(n+1) = T(n)+\lfloor \sqrt{n+1} \rfloor$ for all $n \geq 1$ The value of $T(m^2)$ for $m \geq 1$ is

$m$ identical balls are to be placed in $n$ distinct bags. You are given that $m \geq kn$, where $k$ is a natural number $\geq 1$. In how many ways can the balls be placed in the bags if each bag must contain at least $k$ balls?

Consider the following formula and its two interpretations $I_1$ and $I_2$. $\alpha: (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] \Rightarrow (\forall x)\left[\neg P_x\right]$ $I_1$ : Domain: the set of natural numbers $P_x$ = '$x$ is a prime number' $Q_{xy}$ = '$y$ divides $x$' …

Which of the following is a valid first order formula? (Here $\alpha$ and $\beta$ are first order formulae with $x$ as their only free variable)

Let $(S, \leq)$ be a partial order with two minimal elements a and b, and a maximum element c. Let P: S $\to$ {True, False} be a predicate defined on S. Suppose that P(a) = True, P(b) = False and P(x) $\implies$ P(y) for all $x, y \in S$ satisfying $x \leq y$, where $\implies$ stands for logical implication. Which of the following statements …

Consider the following SQL query Select distinct $a_1, a_2, …, a_n$ from $r_1, r_2, …, r_m$ where P For an arbitrary predicate P, this query is equivalent to which of the following relational algebra expressions?

Which of the following scenarios may lead to an irrecoverable error in a database system?

Which of the following functionality must be implemented by a transport protocol over and above the network protocol?

Which of the following assertions is FALSE about the Internet Protocol (IP)?

In a system with $\text{32 bit}$ virtual addresses and $\text{1 KB}$ page size, use of one-level page tables for virtual to physical address translation is not practical because of

Using a larger block size in a fixed block size file system leads to