GATE CS question library

Consider a relation $R (A, B, C, D, E)$ with the following three functional dependencies. $AB \rightarrow C; \; BC \rightarrow D; \; C \rightarrow E;$ The number of superkeys in the relation $R$ is ______________ .

The number of arrangements of six identical balls in three identical bins is _____________ .

The value of the following limit is ________________. $$\lim_{x \rightarrow 0^{+}} \frac{\sqrt{x}}{1-e^{2\sqrt{x}}}$$

Consider the resolution of the domain name $\textsf{www.gate.org.in}$ by a $\text{DNS}$ resolver. Assume that no resource records are cached anywhere across the $\text{DNS}$ servers and that iterative query mechanism is used in the resolution. The number of $\text{DNS}$ query-response pairs involved in completely resolving the domain name is …

A cache memory that has a hit rate of $0.8$ has an access latency $10 \; \text{ns}$ and miss penalty $100 \; \text{ns}.$ An optimization is done on the cache to reduce the miss rate. However, the optimization results in an increase of cache access latency to $15 \; \text{ns},$ whereas the miss penalty is not affected. The minimum hit rate (rounded …

Which one of the following is the closed form for the generating function of the sequence $\{ a_{n} \}_{n \geq 0}$ defined below? $$a_{n} = \left\{\begin{matrix} n + 1, & \text{n is odd} & \\ 1, & \text{otherwise} & \end{matrix}\right.$$

Consider a simple undirected unweighted graph with at least three vertices. If $\textit{A}$ is the adjacency matrix of the graph, then the number of $3–$cycles in the graph is given by the trace of

Which one of the following statements is $\text{FALSE}?$

Consider a digital display system $\text{(DDS)}$ shown in the figure that displays the contents of register $\text{X}.$ A $16 – \text{bit}$ code word is used to load a word in $\text{X},$ either from $\text{S}$ or from $\text{R}.$ $\text{S}$ is a $1024-$word memory segment and $\text{R}$ is a $32-$word register file. Based on the value of …

Consider three floating point numbers $\textit{A, B}$ and $\textit{C}$ stored in registers $\text{R}_{\text{A}}, \text{R}_{\text{B}}$ and $\text{R}_{\text{C}},$ respectively as per $\textsf{IEEE-754}$ single precision floating point format. The $\text{32-bit}$ content stored in these registers $\text{(in hexadecimal form)}$ are as follows. …

Let $\textit{R}_{i}(z)$ and $\textit{W}_{i}(z)$ denote read and write operations on a data element $z$ by a transaction $\textit{T}_{i},$ respectively. Consider the schedule $\textit{S}$ with four transactions. $S: \; R_{4}(x) R_{2}(x) R_{3}(x)R_{1}(y) W_{1}(y) W_{2}(x) W_{3}(y) R_{4}(y)$ Which one of the following serial schedules is conflict …

Consider four processes $\text{P, Q, R,}$ and $\text{S}$ scheduled on a $\text{CPU}$ as per round robin algorithm with a time quantum of $4\text{ units.}$ The processes arrive in the order $\text{P, Q, R, S,}$ all at time $\text{t = 0}.$ There is exactly one context switch from $\text{S}$ to $\text{Q},$ exactly one context switch from …

What is printed by the following $\text{ANSI C}$ program? #include<stdio.h> int main(int argc, char *argv[]) { char a = ‘P’; char b = ‘x’; char c = (a&b) + ‘*’; char d = (a|b) – ‘-’; char e = (a^b) + ‘+’; printf(“%c %c %c\n”, c, d, e); return 0; } $\text{ASCII}$ encoding for relevant characters is given below …

What is printed by the following $\text{ANSI C}$ program? #include<stdio.h> int main (int argc, char *argv[]) { int a[3][3][3] = {{1, 2, 3, 4, 5, 6, 7, 8, 9}, {10, 11, 12, 13, 14, 15, 16, 17, 18}, {19, 20, 21, 22, 23, 24, 25, 26, 27}}; int i = 0, j = 0, k = 0; for ( i = 0; i < 3; i ++) { for ( k = 0; k < 3; k++) printf(“%d”, a[i][j][k]); printf …

Consider solving the following system of simultaneous equations using $\text{LU}$ decomposition. $$x_{1} + x_{2} – 2x_{3} = 4$$ $$x_{1} + 3x_{2} – x_{3} = 7$$ $$2x_{1} + x_{2} – 5x_{3} = 7$$ where $\textit{L}$ and $\textit{U}$ are denoted as …

Consider the following languages: $L_{1} = \{ ww | w \in \{a,b\}^{\ast} \}$ $L_{2} = \{a^{n} b^{n} c^{m} | m,n \geq 0 \}$ $L_{3} = \{a^{m} b^{n} c^{n} | m,n \geq 0 \}$ Which of the following statements is/are $\text{FALSE}?$

Which of the following is/are undecidable?

Consider the following languages: $L_{1} = \{ a^{n} wa^{n} | w \in \{a,b\}^{\ast}\}$ $L_{2} = \{wxw^{R} | w, x \in \{a,b\}^{*}, |w|, |x| > 0 \}$ Note that $w^{R}$ is the reversal of the string $w.$ Which of the following is/are $\text{TRUE}?$

Consider a simple undirected weighted graph $\textit{G},$ all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of $\textit{G}$ is/are $\text{TRUE}?$

The following simple undirected graph is referred to as the Peterson graph. Which of the following statements is/are $\text{TRUE}?$ The size of the largest independent set of the given graph is $3.$ (A subset of vertices of a graph form an independent set if no two vertices of the subset are adjacent.)