GATE CS question library

Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity $\Theta(n)$?

Let $R$ be a binary relation on the set $\{1,2, \ldots, 10\}$, where $(x, y) \in R$ if the product of $x$ and $y$ is square of an integer. Which of the following properties is/are satisfied by $R$?

In a system, numbers are represented using $4$-bit two's complement form. Consider four numbers $N 1=1011, N 2=1101, N 3=1010$ and $N 4=1001$ in the system. Which of the following operations will result in arithmetic overflow?

Which of the following grammars is/are ambiguous?

For a real number $a$, let $I(a)=\int_{-1}^{1}\left(3 x^{2}-a x+1\right) d x$. Which of the following statements is/are true?

The keys $5,28,19,15,26,33,12,17,10$ are inserted into a hash table using the hash function $h(k)=k \bmod 9$. The collisions are resolved by chaining. After all the keys are inserted, the length of the longest chain is $\_\_\_\_$. (answer in integer)

Consider the system of linear equations given below. $$\begin{array}{c} a x+y=b \\ 16 x+a y=24 \end{array}$$ Suppose the values of $a$ and $b$ are chosen such that the system of linear equations produce multiple solutions. Then the product of $a$ and $b$ is $\_\_\_\_$. (answer in integer)

Consider an array $A=[10,7,8,19,41,35,25,31]$. Suppose the merge sort algorithm is executed on array $A$ to sort it in increasing order. The merge sort algorithm will carry out a total of $7$ merge operations. A merge operation on sorted left array $L$ and sorted right array $R$ is said to be void if the output of the merge operation is the …

If an IP network uses a subnet mask of $255.255.240.0$, the maximum number of IP addresses that can be assigned to network interfaces is $\_\_\_\_$. (answer in integer)

The $32$-bit $\text{IEEE}$ $754$ single precision representation of a number is $0\text{xC}2710000$. The number in decimal representation is $\_\_\_\_$. (rounded off to two decimal places)

A lexical analyzer uses the following token definitions ${letter → [A-Za-z]}$ ${digit → [0-9]}$ ${id → letter (letter | digit)^*}$ ${number → digit}$ ${ }^{+}$ ${ws → (blank | tab| newline)}$ ${ }^{+}$ For the string given below, …

Consider a complete graph $K_{n}$ with $n$ vertices ( $n>4$ ). Note that multiple spanning trees can be constructed over $K_{n}$. Each of these spanning trees is represented as a set of edges. The Jaccard coefficient between any two sets is defined as the ratio of the size of the intersection of the two sets to the size of the union of the two …

Let $G$ be a weighted directed acyclic graph with $m$ edges and $n$ vertices. Given $G$ and a source vertex $s$ in $G$, which one of the following options gives the worst case time complexity of the fastest algorithm to find the lengths of shortest paths from $s$ to all vertices that are reachable from $s$ in ${G}?$

Consider an array $A$ of integers of size $n$. The indices of $A$ run from $1$ to $n$. An algorithm is to be designed to check whether $A$ satisfies the condition given below. $\forall i, j \in\{1, \ldots, n-1\}$ such that $i>j,(A[i+1]-A[i])>(A[j+1]-A[j])$ Which one of the following gives the worst case time complexity of the fastest …

Consider a table $T$, where the elements $T[i][j], 0 \leq i, j \leq n$, represent the cost of the optimal solutions of different subproblems of a problem that is being solved using a dynamic programming algorithm. The recursive formulation to compute the table entries is as follows: …

Consider the following $4$-variable Boolean function $$F(A, B, C, D)=\Sigma m(0,1,2,3,8,9,10,11)$$ Consider $A$ as MSB, $D$ as LSB. Which one of the following options represents the minimal sum of products form for the above function? Note: ${+}$ is OR operation, ${\cdot}$ is AND operation, ${\prime}$ is NOT operation

Consider the canonical $L R(0)$ parsing of the grammar below using terminals $\{a, b, c\}$ and non-terminals $\{A, B, C, S\}$ with $S$ as the start symbol. $$\begin{array}{l} S \rightarrow A C B \\ A \rightarrow a A \mid \epsilon \\ C \rightarrow c C \mid \epsilon \\ B \rightarrow b B \mid b \end{array}$$ Which one of the following options gives the …

In the context of schema normalization in relational DBMS, consider a set $\text{F}$ of functional dependencies. The set of all functional dependencies implied by $\text{F}$ is called the closure of $\text{F}$. To compute the closure of $\text{F}$, Armstrong's Axioms can be applied. Consider $X, Y$, and $Z$ as sets of attributes over a relational …

Consider the transmission of data bits $110001011$ over a link that uses Cyclic Redundancy Check (CRC) code for error detection. If the generator bit pattern is given to be $1001$, which one of the following options shows the remainder bit pattern appended to the data bits before transmission?

Consider the control flow graph given below. Which one of the following options is the set of live variables at the exit point of each basic block?