GATE CS question library

Database table by name $\text{Loan\_Records}$ is given below. …

A deterministic finite automaton ($\text{DFA}$) $D$ with alphabet $\Sigma = \{a, b\}$ is given below. Which of the following finite state machines is a valid minimal $\text{DFA}$ which accepts the same languages as $D$?

An application loads $100$ libraries at startup. Loading each library requires exactly one disk access. The seek time of the disk to a random location is given as $10$ ms. Rotational speed of disk is $6000$ rpm. If all $100$ libraries are loaded from random locations on the disk, how long does it take to load all libraries? (The time to transfer data …

An $8\text{KB}$ direct-mapped write-back cache is organized as multiple blocks, each size of $32\text{-bytes}$. The processor generates $32\text{-bit}$ addresses. The cache controller contains the tag information for each cache block comprising of the following. $1$ valid bit $1$ modified bit As many bits as the minimum needed to identify the …

Definition of a language $L$ with alphabet $\{a\}$ is given as following.$$L = \left\{a^{nk} \mid k > 0, \:\: and \:\: n \text{ is a positive integer constant} \right\}$$What is the minimum number of states needed in a DFA to recognize $L$?

Consider the matrix as given below. $$\begin{bmatrix} 1 & 2 & 3 \\ 0 & 4 & 7 \\ 0 & 0 & 3\end{bmatrix}$$ Which one of the following options provides the CORRECT values of the eigenvalues of the matrix?

Consider an instruction pipeline with four stages $\text{(S1, S2, S3 and S4)}$ each with combinational circuit only. The pipeline registers are required between each stage and at the end of the last stage. Delays for the stages and for the pipeline registers are as given in the figure. What is the approximate speed up of the pipeline in steady state under …

Consider a relational table $r$ with sufficient number of records, having attributes $A_1, A_2, \dots ,A_n$ and let $1 \leq p \leq n$. Two queries $Q1$ and $Q2$ are given below. $Q1: \pi_{A_1, \dots ,A_p} \left(\sigma_{A_p=c}\left(r\right)\right)$ where $c$ is a constant …

Four Matrices $M_1, M_2, M_3$ and $M_4$ of dimensions $p \times q, \:\:q \times r, \:\:r \times s$ and $s \times t$ respectively can be multiplied in several ways with different number of total scalar multiplications. For example when multiplied as $((M_1 \times M_2) \times (M_3 \times M_4))$, the total number of scalar multiplications is …

Which of the given options provides the increasing order of asymptotic complexity of functions $f_1, f_2, f_3$ and $f_4$? $f_1(n) = 2^n$ $f_2(n) = n^{3/2}$ $f_3(n) = n \log_2 n$ $f_4(n) = n^{\log_2 n}$

Consider evaluating the following expression tree on a machine with load-store architecture in which memory can be accessed only through load and store instructions. The variables $a, b, c, d,$ and $e$ are initially stored in memory. The binary operators used in this expression tree can be evaluated by the machine only when operands are in registers. The …

A deck of $5$ cards (each carrying a distinct number from $1$ to $5$) is shuffled thoroughly. Two cards are then removed one at a time from the deck. What is the probability that the two cards are selected with the number on the first card being one higher than the number on the second card?

Consider a finite sequence of random values $X=[x_1,x_2,\dots x_n]$. Let $\mu_x$ be the mean and $\sigma_x$ be the standard deviation of $X$. Let another finite sequence $Y$ of equal length be derived from this as $y_i=a*x_i+b$, where $a$ and $b$ are positive constants. Let $\mu_y$ be the mean and $\sigma_y$ be the standard deviation of …

Consider a database table T containing two columns $\text{X}$ and $\text{Y}$ each of type $\text{integer}$. After the creation of the table, one record $\text{(X=1, Y=1)}$ is inserted in the table. Let $\text{MX}$ and $\text{MY}$ denote the respective maximum values of $\text{X}$ and $\text{Y}$ among all records in the table at any point in …

We are given a set of $n$ distinct elements and an unlabeled binary tree with $n$ nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?

Which one of the following options is CORRECT given three positive integers $x, y$ and $z$, and a predicate $$P\left(x\right) = \neg \left(x=1\right)\wedge \forall y \left(\exists z\left(x=y*z\right) \Rightarrow \left(y=x\right) \vee \left(y=1\right) \right)$$

Given $i = \sqrt{-1}$, what will be the evaluation of the definite integral $\int \limits_0^{\pi/2} \dfrac{\cos x +i \sin x} {\cos x - i \sin x} dx$ ?

On a non-pipelined sequential processor, a program segment, which is the part of the interrupt service routine, is given to transfer $500$ bytes from an I/O device to memory. Initialize the address register Initialize the count to 500 LOOP: Load a byte from device Store in memory at address given by address register Increment the address register Decrement …

Consider two binary operators $\text{‘} \uparrow \text{’}$ and $\text{‘} \downarrow \text{’}$ with the precedence of operator $\downarrow$ being lower than that of the operator $\uparrow$. Operator $\uparrow$ is right associative while operator $\downarrow$ is left associative. Which one of the following represents the parse tree for expression …

Consider the languages $L1, \:L2 \:and \: L3$ as given below. $L1=\{0^p 1^q \mid p, q \in N\}, \\ L2 = \{0^p 1^q \mid p, q \in N \:and \:p=q\} \: and, \\ L3 = \{0^p 1^q 0^r \mid p, q, r \in N\: and \: p=q=r\}.$ Which of the following statements is NOT TRUE?