GATE CS Engineering Mathematics questions

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?

$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 …

Let $\text{G}$ be an arbitrary graph with $n$ nodes and $k$ components. If a vertex is removed from $\text{G}$, the number of components in the resultant graph must necessarily lie down between

Consider the set $\Sigma^*$ of all strings over the alphabet $\Sigma = \{0, 1\}$. $\Sigma^*$ with the concatenation operator for strings

$n$ couples are invited to a party with the condition that every husband should be accompanied by his wife. However, a wife need not be accompanied by her husband. The number of different gatherings possible at the party is

Let $A$ be a sequence of $8$ distinct integers sorted in ascending order. How many distinct pairs of sequences, $B$ and $C$ are there such that each is sorted in ascending order, $B$ has $5$ and $C$ has $3$ elements, and the result of merging $B$ and $C$ gives $A$

Let $P(E)$ denote the probability of the event $E$. Given $P(A) = 1$, $P(B) =\dfrac{1}{2}$, the values of $P(A\mid B)$ and $P(B\mid A)$ respectively are

The binary relation $S= \phi \text{(empty set)}$ on a set $A = \left \{ 1,2,3 \right \}$ is

Four fair coins are tossed simultaneously. The probability that at least one head and one tail turn up is

The maximum number of edges in a $n$-node undirected graph without self loops is

"If $X$ then $Y$ unless $Z$" is represented by which of the following formulas in propositional logic? ("$\neg$" is negation, "$\land$" is conjunction, and "$\rightarrow$" is implication)

Which of the following is true?

The minimum number of colours required to colour the vertices of a cycle with $n$ nodes in such a way that no two adjacent nodes have the same colour is

The rank of the matrix $\begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix}$ is