GATE 2016 Computer Science Session 1 questions and solutions

# Recent questions tagged gate2016-1

1
The delays of NOR gates, Multiplexer and Inverters are 2ns, 1.5ns and 1ns respectively. If all the inputs P, Q, R, S and T are applied at the same time instant, Then the Maximum propagation delay (in ns) of the circuit is _______________
2
Consider the transition diagram of a PDA given below with input alphabet $\Sigma=\{a,b\}$ and stack alphabet $\Gamma = \{X,Z\}$. $Z$ is the initial stack symbol. Let $L$ ... machine that halts on every input $L =\{a^n\mid n \geq0 \} \cup \{a^nb^n \mid n \geq 0\}$ and is deterministic context-free
3
Consider the weighted undirected graph with $4$ vertices, where the weight of edge $\{i,j\}$ is given by the entry $W_{ij}$ in the matrix $W$. W=$\begin{bmatrix} 0&2 &8 &5 \\ 2&0 &5 &8 \\ 8&5 &0 &x \\ 5& 8 &x &0 \end{bmatrix}$ The largest possible integer value of $x$, for which at least one shortest path between some pair of vertices will contain the edge with weight $x$ is ___________.
4
What will be the output of the following $C$ program? void count (int n) { static int d=1; printf ("%d",n); printf ("%d",d); d++; if (n>1) count (n-1); printf ("%d",d); } void main(){ count (3); } $3 \ 1 \ 2 \ 2 \ 1 \ 3 \ 4 \ 4 \ 4$ $3 \ 1 \ 2 \ 1 \ 1 \ 1 \ 2 \ 2 \ 2$ $3 \ 1 \ 2 \ 2 \ 1 \ 3 \ 4$ $3 \ 1 \ 2 \ 1 \ 1 \ 1 \ 2$
5
$G=(V, E)$ is an undirected simple graph in which each edge has a distinct weight, and $e$ is a particular edge of $G$. Which of the following statements about the minimum spanning trees $(MSTs)$ of $G$ is/are TRUE? If $e$ is the lightest edge of some cycle in $G$, then ... heaviest edge of some cycle in $G$, then every MST of $G$ excludes $e$. I only. II only. Both I and II. Neither I nor II.
6
Let $G$ be a complete undirected graph on $4$ vertices, having $6$ edges with weights being $1, 2, 3, 4, 5,$ and $6$. The maximum possible weight that a minimum weight spanning tree of $G$ can have is __________
7
Consider the two cascade $2$ to $1$ multiplexers as shown in the figure . The minimal sum of products form of the output $X$ is $\overline{P} \ \overline {Q}+PQR$ $\overline{P} \ {Q}+QR$ $PQ +\overline{P} \ \overline{Q}R$ $\overline{Q} \ \overline{R} + PQR$
8
Let $X$ be a recursive language and $Y$ be a recursively enumerable but not recursive language. Let $W$ and $Z$ be two languages such that $\overline{Y}$ reduces to $W$, and $Z$ reduces to $\overline{X}$ (reduction means the standard many-one reduction) ... is recursively enumerable. $W$ is not recursively enumerable and $Z$ is recursive. $W$ is not recursively enumerable and $Z$ is not recursive.
9
For a host machine that uses the token bucket algorithm for congestion control, the token bucket has a capacity of $1$ $\text{megabyte}$ and the maximum output rate is $20$ $\text{megabytes}$ per $\text{second}$. Tokens arrive at a rate to sustain output at a ... machine needs to send $12$ $\text{megabytes}$ of data. The minimum time required to transmit the data is _____________ $\text{seconds}$.
10
Consider the following proposed solution for the critical section problem. There are $n$ processes : $P_0....P_{n-1}$. In the code, function $\text{pmax}$ returns an integer not smaller than any of its arguments .For all $i,t[i]$ is ... process can be in the critical section at any time The bounded wait condition is satisfied The progress condition is satisfied It cannot cause a deadlock
11
A function $f: \Bbb{N^+} \rightarrow \Bbb{N^+}$ , defined on the set of positive integers $\Bbb{N^+}$,satisfies the following properties: $f(n)=f(n/2)$ if $n$ is even $f(n)=f(n+5)$ if $n$ is odd Let $R=\{ i \mid \exists{j} : f(j)=i \}$ be the set of distinct values that $f$ takes. The maximum possible size of $R$ is ___________.
12
Cylinder a disk queue with requests for $I/O$ to blocks on cylinders $47, 38, 121, 191, 87, 11, 92, 10.$ The C-LOOK scheduling algorithm is used. The head is initially at cylinder number $63$, moving towards larger cylinder numbers on its ... The cylinders are numbered from $0$ to $199$. The total head movement (in number of cylinders) incurred while servicing these requests is__________.
13
Consider the recurrence relation $a_1 =8 , a_n =6n^2 +2n+a_{n-1}$. Let $a_{99}=K\times 10^4$. The value of $K$ is __________.
14
An IP datagram of size $1000$ $\text{bytes }$arrives at a router. The router has to forward this packet on a link whose MTU (maximum transmission unit) is $100$ $\text{bytes }$. Assume that the size of the IP header is $20$ $\text{bytes }.$ The number of fragments that the IP datagram will be divided into for transmission is________.
15
Consider a computer system with ten physical page frames. The system is provided with an access sequence $(a_{1}, a_{2},....,a_{20}, a_{1}, a_{2},...a_{20})$, where each $a_{i}$ is a distinct virtual page number. The difference in the number of page faults between the last-in-first-out page replacement policy and the optimal page replacement policy is_________.
16
Consider the following experiment. Step 1. Flip a fair coin twice. Step 2. If the outcomes are (TAILS, HEADS) then output $Y$ and stop. Step 3. If the outcomes are either (HEADS, HEADS) or (HEADS, TAILS), then output $N$ and stop. Step 4. If the outcomes are (TAILS, TAILS), then go to Step 1. The probability that the output of the experiment is $Y$ is (up to two decimal places)
17
An operator $delete(i)$ for a binary heap data structure is to be designed to delete the item in the $i$-th node. Assume that the heap is implemented in an array and $i$ refers to the $i$-th index of the array. If the heap tree has depth $d$ (number of edges on the path from the root to the farthest leaf ), ... ? $O(1)$ $O(d)$ but not $O(1)$ $O(2^d)$ but not $O(d)$ $O(d \ 2^d)$ but not $O(2^d)$
18
Consider the following context-free grammars; $G_1 : S \to aS \mid B, B \to b \mid bB$ $G_2 : S \to aA \mid bB, A \to aA \mid B \mid \varepsilon,B \to bB \mid \varepsilon$ Which one of the following pairs of languages is generated by $G_1$ and $G_2$ ... $\{ a^mb^n \mid m \geq 0 \text{ and } n >0\}$ and $\{ a^mb^n \mid m > 0 \text{ or } n>0\}$
19
The following function computes the maximum value contained in an integer array $P[ \ ]$ of size $n$ $(n>=1)$. int max (int *p,int n) { int a = 0, b=n-1; while (__________) { if (p[a]<= p[b]) {a = a+1;} else {b = b-1;} } return p[a]; } The missing loop condition is: $a\ \ != n$ $b\ \ != 0$ $b>(a+1)$ $b\ \ != a$
20
Consider the following two phase locking protocol. Suppose a transaction $T$ accesses (for read or write operations), a certain set of objects $\{O_1,\ldots,O_k \}$ ... and deadlock-freedom guarantee neither serializability nor deadlock-freedom guarantee serializability but not deadlock-freedom guarantee deadlock-freedom but not serializability.
21
What will be the output of the following pseudo-code when parameters are passed by reference and dynamic scoping is assumed? a = 3; void n(x) { x = x * a; print (x); } void m(y) { a = 1 ; a = y - a; n(a); print (a); } void main () { m(a); } $6,2$ $6,6$ $4,2$ $4,4$
22
Consider the following Syntax Directed Translation Scheme $( SDTS )$, with non-terminals $\{S,A \}$ and terminals $\{a,b \}$. $S \to aA \quad \{\text{print }1\}$ $S \to a \quad \{\text{print }2\}$ $A \to Sb \quad \{\text{print }3\}$ Using the above $SDTS$ , the output printed by a bottom-up parser, for the input $aab$ is: $1 \ 3 \ 2$ $2 \ 2 \ 3$ $2 \ 3 \ 1$ syntax error
23
The size of the data count register of a $\text{DMA}$ controller is $16 \text{bits}$. The processor needs to transfer a file of $29,154$ kilobytes from disk to main memory. The memory is byte addressable. The minimum number of times the $\text{DMA}$ controller needs to get the control of the system bus from the processor to transfer the file from the disk to main memory is _________-.
24
The attribute of three arithmetic operators in some programming language are given below. $\begin{array}{|c|l|}\hline \textbf{OPERATOR} & \textbf{PRECEDENCE} & \textbf{ASSOCIATIVITY} & \textbf{ARITY} \\\hline \text{$ ... $2-5+1-7*3$ in this language is ________.
25
A sender uses the Stop-and-Wait ARQ protocol for reliable transmission of frames. Frames are of size $1000$ bytes and the transmission rate at the sender is $80$ Kbps (1 Kbps = 1000 bits/second). Size of an acknowledgment is $100$ bytes and the transmission ... $100$ milliseconds. Assuming no frame is lost, the sender throughput is ________ bytes/ second.
26
Consider that $B$ wants to send a message $m$ that is digitally signed to $A$. Let the pair of private and public keys for $A$ and $B$ be denoted by ${K_{x}}^-$ and ${K_{x}}^+$ for $x=A, B$, respectively. Let $K_{x}(m)$ represent the operation of encrypting $m$ with a key $K_{x}$ and $H(m)$ ... $\left\{m, {K_{A}}^-(H(m))\right\}$ $\left\{m, {K_{A}}^+(m)\right\}$
27
The coefficient of $x^{12}$ in $\left(x^{3}+x^{4}+x^{5}+x^{6}+\dots \right)^{3}$ is ___________.
The stage delays in a $4$-stage pipeline are $800, 500, 400$ and $300$ picoseconds. The first stage (with delay $800$ picoseconds) is replaced with a functionality equivalent design involving two stages with respective delays $600$ and $350$ picoseconds. The throughput increase of the pipeline is ___________ percent.
Consider a computer system with $40$-bit virtual addressing and page size of sixteen kilobytes. If the computer system has a one-level page table per process and each page table entry requires $48$ bits, then the size of the per-process page table is __________ megabytes.
Consider a carry look ahead adder for adding two n-bit integers, built using gates of fan-in at most two. The time to perform addition using this adder is $\Theta (1)$ $\Theta (\log(n))$ $\Theta (\sqrt{n})$ $\Theta (n)$)