GATE CS question library

Let $A$ be a $2 \times 2$ matrix as given. $$A=\left[\begin{array}{rr} 1 & 1 \\ 1 & -1 \end{array}\right]$$ What are the eigenvalues of the matrix $A^{13}$ ?

Consider the following four variable Boolean function in sum-of-product form $$F\left(b_{3}, b_{2}, b_{1}, b_{0}\right)=\sum(0,2,4,8,10,11,12)$$ where the value of the function is computed by considering $b_{3} b_{2} b_{1} b_{0}$ as a $4$-bit binary number, where $b_{3}$ denotes the most significant bit and $b_{0}$ denotes the least significant bit. …

Let $G(V, E)$ be an undirected and unweighted graph with $100$ vertices. Let $d(u, v)$ denote the number of edges in a shortest path between vertices $u$ and $v$ in $V$. Let the maximum value of $d(u, v), u, v \in V$ such that $u \neq v$, be $30$. Let $T$ be any breadth-first-search tree of $G$. Which ONE of the given options is CORRECT …

Consider the following two languages over the alphabet $\{a, b\}$: $$\begin{array}{l} L_{1}=\left\{\alpha \beta \alpha \mid \alpha \in\{a, b\}^{+} \text{AND } \beta \in\{a, b\}^{+}\right\} \\ L_{2}=\left\{\alpha \beta \alpha \mid \alpha \in\{a\}^{+} \text{AND } \beta \in\{a, b\}^{+}\right\} \end{array}$$ Which ONE of the following statements is CORRECT?

Consider the following two languages over the alphabet $\{a, b, c\}$, where $m$ and $n$ are natural numbers. $$\begin{aligned} L_{1} & =\left\{a^{m} b^{m} c^{m+n} \mid m, n \geq 1\right\} \\ L_{2} & =\left\{a^{m} b^{n} c^{m+n} \mid m, n \geq 1\right\} \end{aligned}$$ Which ONE of the following statements is CORRECT?

Which of the following statement(s) is/are TRUE while computing $\operatorname{First}$ and $\operatorname{Follow}$ during top down parsing by a compiler?

Which of the following predicate logic formulae/formula is/are CORRECT representation(s) of the statement: "Everyone has exactly one mother"? The meanings of the predicates used are: mother $(y, x): y$ is the mother of $x$ noteq $(x, y): x$ and $y$ are not equal

Consider a relational schema team $\text{(name,city,owner)}$, with functional dependencies $\{\text{name} \rightarrow \text{city}, \text{name} \rightarrow \text{owner} \}$. The relation team is decomposed into two relations, $\text{t1(name,city)}$ and $\text{t2(name, owner)}$. Which of the following statement(s) is/are TRUE?

$A=\{0,1,2,3, \ldots\}$ is the set of non-negative integers. Let $F$ be the set of functions from $A$ to itself. For any two functions, $f_{1}, f_{2} \in \mathrm{~F}$, we define $$\left(f_{1} \odot f_{2}\right)(n)=f_{1}(n)+f_{2}(n)$$ for every number $n$ in $A$. Which of the following is/are CORRECT about the mathematical structure …

A disk of size $512 \text{ M}$ bytes is divided into blocks of $64 \text{ K}$ bytes. A file is stored in the disk using linked allocation. In linked allocation, each data block reserves $4$ bytes to store the pointer to the next data block. The link part of the last data block contains a NULL pointer (also of $4$ bytes). Suppose a file of …

Consider the following deterministic finite automaton (DFA) defined over the alphabet, $\Sigma=\{a, b\}$. Identify which of the following language(s) is/are accepted by the given DFA.

Refer to the given $3$-address code sequence. This code sequence is split into basic blocks. The number of basic blocks is ________. (Answer in integer) 1001: i = 1 1002: j = 1 1003: t1 = 10*i 1004: t2 = t1+j 1005: t3 = 8*t2 1006: t4 = t3-88 1007: a[t4] = 0.0 1008: j = j+1 1009: if j <= 10 goto 1003 1010: i = i+1 1011: if i <= 10 goto 1002 1012: i = …

A computer has a memory hierarchy consisting of two-level cache $\text{(L1}$ and $\text{L2)}$ and a main memory. If the processor needs to access data from memory, it first looks into $\text{L1}$ cache. If the data is not found in $\text{L1}$ cache, it goes to $\text{L2}$ cache. If it fails to get the data from $\text{L2}$ cache, it goes to main …

In optimal page replacement algorithm, information about all future page references is available to the operating system (OS). A modification of the optimal page replacement algorithm is as follows: The OS correctly predicts only up to next $4$ page references (including the current page) at the time of allocating a frame to a page. A process accesses the …

Consider the following database tables of a sports league. player (pid, pname, age) team(tid, tname, city, cid) coach (cid, cname) members (pid,tid) An instance of the table and an SQL query are given. …

Suppose a $5$-bit message is transmitted from a source to a destination through a noisy channel. The probability that a bit of the message gets flipped during transmission is $0.01$. Flipping of each bit is independent of one another. The probability that the message is delivered error-free to the destination is ___________ (rounded off to three decimal …

Suppose a message of size $15000$ bytes is transmitted from a source to a destination using IPv4 protocol via two routers as shown in the figure. Each router has a defined maximum transmission unit (MTU) as shown in the figure, including IP header. The number of fragments that will be delivered to the destination is _________. (Answer in integer)

Consider a probability distribution given by the density function $P(x)$. $$P(x)=\left\{\begin{aligned} C x^{2}, & \text{ for } 1 \leq x \leq 4 \\ 0, & \text{ for } x<1 \text{ or } x>4 \end{aligned}\right.$$ The probability that $x$ lies between $2$ and $3$, i.e., $P(2 \leq x \leq 3)$ is _________. (rounded off to three decimal …

Consider a finite state machine (FSM) with one input $X$ and one output $f$, represented by the given state transition table. The minimum number of states required to realize this FSM is _______. (Answer in integer). …

Consider the given sequential circuit designed using D-Flip-flops. The circuit is initialized with some value (initial state). The number of distinct states the circuit will go through before returning back to the initial state is ___________. (Answer in integer)