# Recent questions tagged gate2015-cse-set1 65 votes
6 answers
1
The least number of temporary variables required to create a three-address code in static single assignment form for the expression $q + r / 3 + s - t * 5 + u * v/w$ is__________________.
22 votes
5 answers
2
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.
30 votes
5 answers
3
Suppose that the stop-and-wait protocol is used on a link with a bit rate of $64$ $\text{kilobits}$ per second and $20$ $\text{milliseconds}$ propagation delay. Assume that the transmission time for the acknowledgment and the processing time at nodes are negligible. Then the minimum frame size in bytes to achieve a link utilization of at least $50$ $\text{%}$ is_________________.
51 votes
11 answers
4
Consider the DFAs $M$ and $N$ given above. The number of states in a minimal DFA that accept the language $L(M) \cap L(N)$ is_____________.
64 votes
3 answers
5
Consider the NPDA $\left \langle Q= \left \{ q_{0}, q_{1}, q_{2} \right \},\Sigma = \left \{ 0, 1 \right \}, \Gamma = \left \{ 0, 1, \perp \right \}, \delta, q_{0}, \perp, F =\left \{ q_{2} \right \} \right \rangle$ ... is as follows: Which one of the following sequences must follow the string $101100$ so that the overall string is accepted by the automaton? $10110$ $10010$ $01010$ $01001$
45 votes
3 answers
6
A variable $x$ is said to be live at a statement $s_{i}$ in a program if the following three conditions hold simultaneously: There exists a statement $S_{j}$ that uses $x$ There is a path from $S_{i}$ to $S_{j}$ in the flow graph corresponding to the program The path has no intervening assignment ... of the above control flow graph are $\text{p, s, u}$ $\text{r, s, u}$ $\text{r, u}$ $\text{q, v}$
45 votes
4 answers
7
Let a$_{n}$ represent the number of bit strings of length n containing two consecutive $1$s. What is the recurrence relation for $a_{n}$? $a_{n - 2} + a_{n - 1} + 2^{n - 2}$ $a_{n - 2} + 2a_{n - 1} + 2^{n - 2}$ $2a_{n - 2} + a_{n - 1} + 2^{n - 2}$ $2a_{n - 2} + 2a_{n - 1} + 2^{n - 2}$
43 votes
7 answers
8
Consider a disk pack with a seek time of $4$ milliseconds and rotational speed of $10000$ rotations per minute (RPM). It has $600$ sectors per track and each sector can store $512$ bytes of data. Consider a file stored in the disk. The file ... accessing each sector is half of the time for one complete rotation. The total time (in milliseconds) needed to read the entire file is__________________
22 votes
2 answers
9
Consider a main memory with five-page frames and the following sequence of page references: $\text{3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3}$. Which one of the following is true with respect to page replacement policies First In First Out (FIFO) and ... of page faults FIFO incurs $2$ more page faults than LRU LRU incurs $2$ more page faults than FIFO FIFO incurs $1$ more page faults than LRU
73 votes
14 answers
10
Consider a uniprocessor system executing three tasks $T_{1}, T_{2}$ and $T_{3}$ each of which is composed of an infinite sequence of jobs (or instances) which arrive periodically at intervals of $3$, $7$ and $20$ milliseconds, respectively ... the 1st millisecond and task preemptions are allowed, the first instance of $T_{3}$ completes its execution at the end of_____________________milliseconds.
34 votes
9 answers
11
Let $G = (V, E)$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $x \in V$, let $d(x)$ denote the shortest distance in $G$ from $s$ to $x$. A breadth first search (BFS) is performed starting at $s$. Let $T$ ... of $G$ that is not in $T$, then which one of the following CANNOT be the value of $d(u) - d(v)$? $-1$ $0$ $1$ $2$
16 votes
2 answers
12
Compute the value of: $\large \int \limits_{\frac{1}{\pi}}^{\frac{2}{\pi}}\frac{\cos(1/x)}{x^{2}}dx$
56 votes
5 answers
13
The graph shown below has $8$ edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight $36$ and contains the edges: $\{(A, C), (B, C), (B, E), (E, F), (D, F)\}$. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all $8$ edges of this graph is_______________.
9 votes
3 answers
14
Consider the following C program segment. while (first <= last) { if (array[middle] < search) first = middle + 1; else if (array[middle] == search) found = TRUE; else last = middle - 1; middle = (first + last)/2; } if (first > last) notpresent = TRUE; The cyclomatic complexity of the program segment is_______________.
45 votes
6 answers
15
Consider an Entity-Relationship $(ER)$ model in which entity sets E$_{1}$ and E$_{2}$ are connected by an m:n relationship R$_{12}$. E$_{1}$ and E$_{3}$ are connected by a 1 : n (1 on the side of E$_{1}$ and n on the side of ... . If a relational model is derived from the above $ER$ model, then the minimum number of relations that would be generated if all relation are in $3NF$ is________________.
74 votes
5 answers
16
An algorithm performs $(\log N)^{\frac{1}{2}}$ find operations , $N$ insert operations, $(\log N)^{\frac{1}{2}}$ delete operations, and $(\log N)^{\frac{1}{2}}$ decrease-key operations on a set of data items with keys drawn from ... to use, if the goal is to achieve the best total asymptotic complexity considering all the operations? Unsorted array Min - heap Sorted array Sorted doubly linked list
70 votes
6 answers
17
Consider the operations $\textit{f (X, Y, Z) = X'YZ + XY' + Y'Z'}$ and $\textit{g (X, Y, Z) = X'YZ + X'YZ' + XY}$ Which one of the following is correct? Both $\left\{\textit{f} \right\}$ and $\left\{ \textit{g}\right\}$ are functionally ... Only $\left\{ \textit{g}\right\}$ is functionally complete Neither $\left\{ \textit{f}\right\}$ nor $\left\{\textit{g}\right\}$ is functionally complete
44 votes
5 answers
18
Consider a non-pipelined processor with a clock rate of $2.5$ $GHz$ and average cycles per instruction of four. The same processor is upgraded to a pipelined processor with five stages; but due to the internal pipeline delay, the clock speed is reduced to $2$ $GHz$. Assume that there are no stalls in the pipeline. The speedup achieved in this pipelined processor is_______________.
37 votes
7 answers
19
A positive edge-triggered $D$ flip-flop is connected to a positive edge-triggered $JK$ flip-flop as follows. The $Q$ output of the $D$ flip-flop is connected to both the $J$ and $K$ inputs of the $JK$ flip-flop, while the $Q$ output of the $JK$ ... mode of the $JK$ flip-flops. Both the flip-flops have non-zero propagation delays. $0110110\ldots$ $0100100\ldots$ $011101110\ldots$ $011001100\ldots$
21 votes
3 answers
20
Consider the following $2 \times 2$ matrix $A$ where two elements are unknown and are marked by $a$ and $b$. The eigenvalues of this matrix are -1 and 7. What are the values of $a$ and $b$? $\qquad A = \begin{pmatrix}1 & 4\\ b&a \end{pmatrix}$ $a = 6, b = 4$ $a = 4, b = 6$ $a = 3, b = 5$ $a = 5, b = 3$
92 votes
5 answers
21
What is the output of the following C code? Assume that the address of $x$ is $2000$ (in decimal) and an integer requires four bytes of memory. int main () { unsigned int x   = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11, 12}}; printf ("%u, %u, %u", x + 3, *(x + 3), *(x + 2) + 3); } $2036, 2036, 2036$ $2012, 4, 2204$ $2036, 10, 10$ $2012, 4, 6$
52 votes
6 answers
22
Suppose $L = \left\{ p, q, r, s, t\right\}$ is a lattice represented by the following Hasse diagram: For any $x, y \in L$, not necessarily distinct , $x \vee y$ and $x \wedge y$ are join and meet of $x, y$, respectively. Let $L^3 = \left\{\left(x, y, z\right): x, y, z \in L\right\}$ be ... $p_r = 0$ $p_r = 1$ $0 < p_r ≤ \frac{1}{5}$ $\frac{1}{5} < p_r < 1$
46 votes
8 answers
23
Consider the following pseudo code, where $x$ and $y$ are positive integers. begin q := 0 r := x while r ≥ y do begin r := r - y q := q + 1 end end The post condition that needs to be satisfied after the program terminates is $\{ r = qx + y \wedge r < y\}$ $\{ x = qy + r \wedge r < y\}$ $\{ y = qx + r \wedge 0 < r < y\}$ $\{ q + 1 < r - y \wedge y > 0\}$
23 votes
3 answers
24
Consider a max heap, represented by the array: $40, 30, 20, 10, 15, 16, 17, 8, 4$ ... $40, 30, 20, 10, 35, 16, 17, 8, 4, 15$ $40, 35, 20, 10, 15, 16, 17, 8, 4, 30$
44 votes
9 answers
25
Consider the following C function. int fun1 (int n) { int i, j, k, p, q = 0; for (i = 1; i < n; ++i) { p = 0; for (j = n; j > 1; j = j/2) ++p; for (k = 1; k < p; k = k * 2) ++q; } return q; } Which one of the following most closely approximates the return value of the function fun1? $n^3$ $n(\log n)^2$ $n \log n$ $n \log(\log n)$
38 votes
8 answers
26
Consider a LAN with four nodes $S_1, S_2, S_3,$ and $S_4$. Time is divided into fixed-size slots, and a node can begin its transmission only at the beginning of a slot. A collision is said to have occurred if more than one node transmits in the ... and $0.4$ respectively. The probability of sending a frame in the first slot without any collision by any of these four stations is__________________.
34 votes
5 answers
27
$\sum\limits_{x=1}^{99}\frac{1}{x(x+1)}$ = __________________.
20 votes
4 answers
28
Suppose that everyone in a group on $N$ people wants to communicate secretly with the $(\text{N - 1})$ others using symmetric Key cryptographic system. The communication between any two person should not be decodable by the others in the group. The numbers of keys required in the system as a whole to satisfy the confidentiality requirement is $2N$ $N(N-1)$ $\dfrac{N(N-1)}{2}$ $(N-1)^{2}$
26 votes
3 answers
29
In the LU decomposition of the matrix $\begin{bmatrix}2 & 2 \\ 4 & 9\end{bmatrix}$, if the diagonal elements of $U$ are both $1$, then the lower diagonal entry $l_{22}$ of $L$ is_________________.
49 votes
5 answers
30
For a set $A$, the power set of $A$ is denoted by $2^{A}$. If $A = \left\{5,\left\{6\right\}, \left\{7\right\}\right\}$, which of the following options are TRUE? $\varnothing \in 2^{A}$ $\varnothing \subseteq 2^{A}$ $\left\{5,\left\{6\right\}\right\} \in 2^{A}$ $\left\{5,\left\{6\right\}\right\} \subseteq 2^{A}$ I and III only II and III only I, II and III only I, II and IV only