GATE CS question library

$F$ is an $n\times n$ real matrix. $b$ is an $n\times 1$ real vector. Suppose there are two $n\times 1$ vectors, $u$ and $v$ such that, $u ≠ v$ and $Fu = b, Fv = b$. Which one of the following statements is false?

Let $E, F$ and $G$ be finite sets. Let $X = (E ∩ F) - (F ∩ G)$ and $Y = (E - (E ∩ G)) - (E - F)$. Which one of the following is true?

For each element in a set of size $2n$, an unbiased coin is tossed. The $2n$ coin tosses are independent. An element is chosen if the corresponding coin toss was a head. The probability that exactly $n$ elements are chosen is

Consider the following log sequence of two transactions on a bank account, with initial balance $12000,$ that transfer $2000$ to a mortgage payment and then apply a $5\%$ interest. T1 start T1 B old $=12000$ new $=10000$ T1 M old $=0$ new $=2000$ T1 commit T2 start T2 B old $=10000$ new $=10500$ T2 commit Suppose the database system crashes …

Let $L_1=\{0^{n+m}1^n0^m\mid n,m\geq 0 \}$, $L_2=\{0^{n+m}1^{n+m}0^m\mid n,m\geq 0\}$ and $L_3=\{0^{n+m}1^{n+m}0^{n+m}\mid n,m\geq 0\}$. Which of these languages are NOT context free?

We are given a set $X = \{X_1,\ldots,X_n\}$ where $X_i=2^i$. A sample $S\subseteq X$ is drawn by selecting each $X_i$ independently with probability $P_i = \frac{1}{2}$ . The expected value of the smallest number in sample $S$ is:

An element in an array $X$ is called a leader if it is greater than all elements to the right of it in $X$. The best algorithm to find all leaders in an array

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?

Consider the following C-program fragment in which $i$, $j$ and $n$ are integer variables. for( i = n, j = 0; i > 0; i /= 2, j +=i ); Let $val(j)$ denote the value stored in the variable $j$ after termination of the for loop. Which one of the following is true?

Which one of the following in place sorting algorithms needs the minimum number of swaps?

A scheme for storing binary trees in an array $X$ is as follows. Indexing of $X$ starts at $1$ instead of $0$. the root is stored at $X[1]$. For a node stored at $X[i]$, the left child, if any, is stored in $X[2i]$ and the right child, if any, in $X[2i+1]$. To be able to store any binary tree on n vertices the minimum size of $X$ should be

To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:

Consider a weighted complete graph $G$ on the vertex set $\{v_1,v_2,.....v_n\}$ such that the weight of the edge $(v_i, v_j)$ is $2|i-j|$. The weight of a minimum spanning tree of $G$ is:

In a binary max heap containing $n$ numbers, the smallest element can be found in time

A CPU has $24$-$bit$ instructions. A program starts at address $300$ (in decimal). Which one of the following is a legal program counter (all values in decimal)?

You are given a free running clock with a duty cycle of $50\%$ and a digital waveform $f$ which changes only at the negative edge of the clock. Which one of the following circuits (using clocked D flip-flops) will delay the phase of $f$ by $180°$?

Consider the following grammar $S \rightarrow S * E$ $S \rightarrow E$ $E \rightarrow F + E$ $E \rightarrow F$ $F \rightarrow id$ Consider the following LR(0) items corresponding to the grammar above $S \rightarrow S *.E$ $E \rightarrow F. + E$ $E \rightarrow F + .E$ Given the items above, which two of them will appear in the same set in the …

Consider three CPU-intensive processes, which require $10$, $20$ and $30$ time units and arrive at times $0$, $2$ and $6$, respectively. How many context switches are needed if the operating system implements a shortest remaining time first scheduling algorithm? Do not count the context switches at time zero and at the end.

For which one of the following reasons does internet protocol(IP) use the time-to-live(TTL) field in IP datagram header?

A relation $R$ is defined on ordered pairs of integers as follows: $$(x,y)R(u,v) \text{ if } x<u \text{ and } y>v$$ Then $R$ is: