The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged gate20161
GATE 2016 Computer Science Session 1 questions and solutions
+26
votes
7
answers
1
GATE2016143
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$ denote the language accepted by the PDA Which one of the following is TRUE? $L =\{a^nb^n\mid n \geq0 ... halts on every input $L =\{a^n\mid n \geq0 \} \cup \{a^nb^n \mid n \geq 0\}$ and is deterministic contextfree
asked
Feb 12, 2016
in
Theory of Computation
by
Sandeep Singh
Loyal
(
7.8k
points)

4k
views
gate20161
theoryofcomputation
pushdownautomata
normal
+25
votes
6
answers
2
GATE2016138
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 ... 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 ___________.
asked
Feb 12, 2016
in
DS
by
Sandeep Singh
Loyal
(
7.8k
points)

5.3k
views
gate20161
datastructure
graphs
normal
numericalanswers
+18
votes
8
answers
3
GATE2016135
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 (n1); 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$
asked
Feb 12, 2016
in
Programming
by
Sandeep Singh
Loyal
(
7.8k
points)

3.4k
views
gate20161
programminginc
recursion
normal
+50
votes
5
answers
4
GATE2016140
$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$, ... 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.
asked
Feb 12, 2016
in
Algorithms
by
Sandeep Singh
Loyal
(
7.8k
points)

5.4k
views
gate20161
algorithms
spanningtree
normal
+37
votes
16
answers
5
GATE2016139
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 __________
asked
Feb 12, 2016
in
Algorithms
by
Sandeep Singh
Loyal
(
7.8k
points)

7k
views
gate20161
algorithms
spanningtree
normal
numericalanswers
+12
votes
3
answers
6
GATE2016130
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$
asked
Feb 12, 2016
in
Digital Logic
by
Sandeep Singh
Loyal
(
7.8k
points)

2.1k
views
gate20161
digitallogic
multiplexer
normal
+25
votes
3
answers
7
GATE2016144
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 ... is recursively enumerable. $W$ is not recursively enumerable and $Z$ is recursive. $W$ is not recursively enumerable and $Z$ is not recursive.
asked
Feb 12, 2016
in
Theory of Computation
by
Sandeep Singh
Loyal
(
7.8k
points)

3.2k
views
gate20161
theoryofcomputation
easy
recursiveandrecursivelyenumerablelanguages
+38
votes
10
answers
8
GATE2016154
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 ... needs to send $12$ $\text{megabytes}$ of data. The minimum time required to transmit the data is _____________ $\text{seconds}$.
asked
Feb 12, 2016
in
Computer Networks
by
Sandeep Singh
Loyal
(
7.8k
points)

8k
views
gate20161
computernetworks
tokenbucket
normal
numericalanswers
+47
votes
5
answers
9
GATE2016150
Consider the following proposed solution for the critical section problem. There are $n$ processes : $P_0....P_{n1}$. In the code, function $\text{pmax}$ returns an integer not smaller than any of its arguments .For all $i,t[i]$ is ... 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
asked
Feb 12, 2016
in
Operating System
by
Sandeep Singh
Loyal
(
7.8k
points)

7.9k
views
gate20161
operatingsystem
resourceallocation
difficult
ambiguous
+37
votes
5
answers
10
GATE2016128
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 ___________.
asked
Feb 12, 2016
in
Set Theory & Algebra
by
Sandeep Singh
Loyal
(
7.8k
points)

4k
views
gate20161
settheory&algebra
functions
normal
numericalanswers
+28
votes
7
answers
11
GATE2016148
Cylinder a disk queue with requests for $I/O$ to blocks on cylinders $47, 38, 121, 191, 87, 11, 92, 10.$ The CLOOK scheduling algorithm is used. The head is initially at cylinder number $63$, moving towards larger cylinder numbers on ... The cylinders are numbered from $0$ to $199$. The total head movement (in number of cylinders) incurred while servicing these requests is__________.
asked
Feb 12, 2016
in
Operating System
by
Sandeep Singh
Loyal
(
7.8k
points)

5.5k
views
gate20161
operatingsystem
diskscheduling
normal
numericalanswers
+27
votes
7
answers
12
GATE2016127
Consider the recurrence relation $a_1 =8 , a_n =6n^2 +2n+a_{n1}$. Let $a_{99}=K\times 10^4$. The value of $K$ is __________.
asked
Feb 12, 2016
in
Combinatory
by
Sandeep Singh
Loyal
(
7.8k
points)

5k
views
gate20161
permutationsandcombinations
recurrence
normal
numericalanswers
+17
votes
4
answers
13
GATE2016153
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________.
asked
Feb 12, 2016
in
Computer Networks
by
Sandeep Singh
Loyal
(
7.8k
points)

3.4k
views
gate20161
computernetworks
ippacket
normal
numericalanswers
+28
votes
7
answers
14
GATE2016149
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 lastinfirstout page replacement policy and the optimal page replacement policy is_________.
asked
Feb 12, 2016
in
Operating System
by
Sandeep Singh
Loyal
(
7.8k
points)

4.1k
views
gate20161
operatingsystem
pagereplacement
normal
numericalanswers
+18
votes
3
answers
15
GATE2016129
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)
asked
Feb 12, 2016
in
Probability
by
Sandeep Singh
Loyal
(
7.8k
points)

2.7k
views
gate20161
probability
normal
numericalanswers
+24
votes
3
answers
16
GATE2016137
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 ... $O(1)$ $O(d)$ but not $O(1)$ $O(2^d)$ but not $O(d)$ $O(d \ 2^d)$ but not $O(2^d)$
asked
Feb 12, 2016
in
DS
by
Sandeep Singh
Loyal
(
7.8k
points)

3.1k
views
gate20161
datastructure
heap
normal
+29
votes
7
answers
17
GATE2016142
Consider the following contextfree 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 generaed by $G_1$ and $G_2$ ,respectively? $\{ a^mb^n \mid m > 0 \ ... $\{ a^mb^n \mid m \geq 0 \ and \ n >0\} \ and \ \{ a^mb^n \mid m > 0 \ or \ n>0\}$
asked
Feb 12, 2016
in
Theory of Computation
by
Sandeep Singh
Loyal
(
7.8k
points)

3.2k
views
gate20161
theoryofcomputation
contextfreelanguage
normal
+15
votes
1
answer
18
GATE2016134
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=n1; while (__________) { if (p[a]<= p[b]) {a = a+1;} else {b = b1;} } return p[a]; } The missing loop condition is: $a != n$ $b != 0$ $b>(a+1)$ $b != a$
asked
Feb 12, 2016
in
Programming
by
Sandeep Singh
Loyal
(
7.8k
points)

2k
views
gate20161
programminginc
normal
+28
votes
5
answers
19
GATE2016151
Consider the following two phase locking protocol. Suppose a transaction $T$ accesses (for read or write operations), a certain set of objects $\{O_1,....O_k \}$. This is done in the following manner: $\text ... deadlockfreedom guarantee neither serializability nor deadlockfreedom guarantee serializability but not deadlockfreedom guarantee deadlockfreedom but not serializability.
asked
Feb 12, 2016
in
Databases
by
Sandeep Singh
Loyal
(
7.8k
points)

3.8k
views
gate20161
databases
transactions
normal
+31
votes
4
answers
20
GATE2016136
What will be the output of the following pseudocode 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$
asked
Feb 12, 2016
in
Compiler Design
by
Sandeep Singh
Loyal
(
7.8k
points)

5.3k
views
gate20161
parameterpassing
normal
+15
votes
2
answers
21
GATE2016146
Consider the following Syntax Directed Translation Scheme $( SDTS )$, with nonterminals $\{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 bottomup parser, for the input $aab$ is: $1 \ 3 \ 2 $ $2 \ 2 \ 3 $ $2 \ 3 \ 1 $ syntax error
asked
Feb 12, 2016
in
Compiler Design
by
Sandeep Singh
Loyal
(
7.8k
points)

2k
views
gate20161
compilerdesign
syntaxdirectedtranslation
normal
+19
votes
3
answers
22
GATE2016131
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 _________.
asked
Feb 12, 2016
in
CO & Architecture
by
Sandeep Singh
Loyal
(
7.8k
points)

3.5k
views
gate20161
coandarchitecture
dma
normal
numericalanswers
+20
votes
2
answers
23
GATE2016145
The attribute of three arithmetic operators in some programming language are given below. OPERATOR PRECEDENCE ASSOCIATIVITY ARITY $+$ high Left Binary $$ Medium Right Binary $*$ Low Left Binary The value of the expression $25+17*3$ in this language is ________.
asked
Feb 12, 2016
in
Compiler Design
by
Sandeep Singh
Loyal
(
7.8k
points)

2k
views
gate20161
compilerdesign
parsing
normal
numericalanswers
+28
votes
6
answers
24
GATE2016155
A sender uses the StopandWait 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 acknowledgement is $100$ bytes and the ... Kbps. The oneway propagation delay is $100$ milliseconds. Assuming no frame is lost, the sender throughout is ________ bytes/ second.
asked
Feb 12, 2016
in
Computer Networks
by
Sandeep Singh
Loyal
(
7.8k
points)

5.5k
views
gate20161
computernetworks
stopandwait
normal
numericalanswers
+17
votes
2
answers
25
GATE2016152
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)$ ... {B}}^(H(m))\right\}$ $\left\{m, {K_{A}}^(H(m))\right\}$ $\left\{m, {K_{A}}^+(m)\right\}$
asked
Feb 12, 2016
in
Computer Networks
by
Sandeep Singh
Loyal
(
7.8k
points)

2.2k
views
gate20161
computernetworks
networksecurity
easy
+26
votes
8
answers
26
GATE2016126
The coefficient of $x^{12}$ in $\left(x^{3}+x^{4}+x^{5}+x^{6}+\dots \right)^{3}$ is ___________.
asked
Feb 12, 2016
in
Combinatory
by
Sandeep Singh
Loyal
(
7.8k
points)

6.1k
views
gate20161
permutationsandcombinations
generatingfunctions
normal
numericalanswers
+33
votes
5
answers
27
GATE2016132
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.
asked
Feb 12, 2016
in
CO & Architecture
by
Sandeep Singh
Loyal
(
7.8k
points)

5.7k
views
gate20161
coandarchitecture
pipelining
normal
numericalanswers
+14
votes
3
answers
28
GATE2016147
Consider a computer system with $40$bit virtual addressing and page size of sixteen kilobytes. If the computer system has a onelevel page table per process and each page table entry requires $48$ bits, then the size of the perprocess page table is __________ megabytes.
asked
Feb 12, 2016
in
Operating System
by
Sandeep Singh
Loyal
(
7.8k
points)

2.9k
views
gate20161
operatingsystem
virtualmemory
easy
numericalanswers
+29
votes
5
answers
29
GATE2016133
Consider a carry look ahead adder for adding two nbit integers, built using gates of fanin at most two. The time to perform addition using this adder is $\Theta (1)$ $\Theta (\log(n))$ $\Theta (\sqrt{n})$ $\Theta (n)$)
asked
Feb 12, 2016
in
Digital Logic
by
Sandeep Singh
Loyal
(
7.8k
points)

5.6k
views
gate20161
digitallogic
adder
normal
+54
votes
9
answers
30
GATE2016141
Let $Q$ denote a queue containing sixteen numbers and $S$ be an empty stack. $Head(Q)$ returns the element at the head of the queue $Q$ without removing it from $Q$. Similarly $Top(S)$ returns the element at the top of $S$ without removing it from $S$. Consider ... Pop(S); Enqueue (Q, x); end end The maximum possible number of iterations of the while loop in the algorithm is _______.
asked
Feb 12, 2016
in
DS
by
Sandeep Singh
Loyal
(
7.8k
points)

5.5k
views
gate20161
datastructure
queues
difficult
numericalanswers
Page:
1
2
3
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
IISc CSA and CDCS written test and interview Experince
IIIT Hyderabad Interview Experience
My failure, Oh wait SUCCESS journey
ALGORITHMS CHECKLIST:
A Failure who got into IISc
Follow @csegate
Gatecse
Recent questions tagged gate20161
Recent Blog Comments
Sir I didn't get an email for GO classroom, ...
any one with marks less than 125 selected?
Thank you @Arjun Sir, @NamitaAIR1, @Priyanka, ...
Your story is very inspiring for the boys like me ...
So you completed your Btech in 5 yrs? How could ...
36,194
questions
43,647
answers
124,088
comments
42,928
users