Gate2008
Question 2 
If P, Q, R are subsets of the universal set U, then (P∩Q∩R) ∪ (P^{c}∩Q∩R) ∪ Q^{c }∪ R^{c} is
Q^{c} ∪ R^{c}
 
P ∪ Q^{c} ∪ R^{c}
 
P^{c} ∪ Q^{c} ∪ R^{c}
 
U 
Question 2 Explanation:
Given, (P∩Q∩R)∪(P^{c}∩Q∩R)∪Q^{c}∪R^{c}
It can be written as the p.q.r + p'.q.r +q'+r'
=> (p+p').q.r + q' +r'
=> q.r +(q'+r')
=> q.r + q'+r' = 1 i.e U
It can be written as the p.q.r + p'.q.r +q'+r'
=> (p+p').q.r + q' +r'
=> q.r +(q'+r')
=> q.r + q'+r' = 1 i.e U
Question 3 
0  
either 0 or 1  
one of 0, 1 or 1  
any real number

Question 3 Explanation:
The conjugate matrix [AB] is
When a5=0, then rank(A)=rank[AB]<3,
So infinite number of solutions.
But, it is given that the given system has unique solution i.e., rank(A)rank[AB]=3 will be retain only if a5≠0.
When a5=0, then rank(A)=rank[AB]<3,
So infinite number of solutions.
But, it is given that the given system has unique solution i.e., rank(A)rank[AB]=3 will be retain only if a5≠0.
Question 4 
In the IEEE floating point representation, the hexadecimal value 0×00000000 corresponds to
the normalized value 2^{127}  
the normalized value 2^{126}
 
the normalized value +0
 
the special value +0

Question 4 Explanation:
Value is ±0 if M=0 and E=0.
Question 6 
decimal 10
 
decimal 11
 
decimal 10 and 11  
any value >2

Question 6 Explanation:
Any value of r will satisfy the above equation. But the radix should be greater than 2 because the 121 has 2. So r >2 is correct.
Question 7 
The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity
θ(n)  
θ(m)  
θ(m+n)  
θ(mn) 
Question 7 Explanation:
To find the number of connected components using either BFS or DFS time complexity is θ(m+n).
Suppose if we are using Adjacency matrix means it takes θ(n^{2}).
Suppose if we are using Adjacency matrix means it takes θ(n^{2}).
Question 8 
Σm(4,6)  
Σm(4,8)  
Σm(6,8)  
Σm(4,6,8)

Question 8 Explanation:
f= f_{1}* f_{2} + f_{3}
f_{1}*f_{2} is intersection of minterms of f_{1} and f_{2}
f= (f_{1}*f_{2}) + f_{3} is union of minterms of (f_{1}*f_{2}) and f_{3}
Σm(1,6,8,15)= Σm(4,5,6,7,8) * f_{2} + Σm(1,6,15)
Options A, B and D have minterm m_{4} which result in Σm(1,4,6,15), Σm(1,4,6,8, 15) and Σm(1,4,6,8, 15)respectively and they are not equal to f.
Option C : If f_{2}= Σm(6,8)
RHS: Σm(4,5,6,7,8) * Σm(6,8) + Σm(1,6,15)
=Σm(6,8) + Σm(1,6,15)
= Σm(1,6,8,15)
= f= LHS
f_{1}*f_{2} is intersection of minterms of f_{1} and f_{2}
f= (f_{1}*f_{2}) + f_{3} is union of minterms of (f_{1}*f_{2}) and f_{3}
Σm(1,6,8,15)= Σm(4,5,6,7,8) * f_{2} + Σm(1,6,15)
Options A, B and D have minterm m_{4} which result in Σm(1,4,6,15), Σm(1,4,6,8, 15) and Σm(1,4,6,8, 15)respectively and they are not equal to f.
Option C : If f_{2}= Σm(6,8)
RHS: Σm(4,5,6,7,8) * Σm(6,8) + Σm(1,6,15)
=Σm(6,8) + Σm(1,6,15)
= Σm(1,6,8,15)
= f= LHS
Question 9 
Which of the following is true for the language {a^{p}p is a prime} ?
It is not accepted by a Turing Machine
 
It is regular but not contextfree
 
It is contextfree but not regular
 
It is neither regular nor contextfree, but accepted by a Turing machine

Question 9 Explanation:
Finding prime number cannot be done by FA or PDA , so it cannot be regular or CFL. This language can be recognized by LBA , hence it can be accepted by Turing Machine.
Question 10 
I and II  
I and IV  
II and III
 
II and IV

Question 10 Explanation:
The intersection of two regular languages is always a regular language (by closure property of regular language) and testing infiniteness of regular language is decidable. Hence statement I is decidable.
Statement IV is also decidable, we need to check that whether the given grammar satisfies the CFG rule (TYPE 2 grammar productions).
But statements II and III are undecidable, as there doesn’t exist any algorithm to check whether a given contextfree language is regular and whether two pushdown automata accept the same language.
Statement IV is also decidable, we need to check that whether the given grammar satisfies the CFG rule (TYPE 2 grammar productions).
But statements II and III are undecidable, as there doesn’t exist any algorithm to check whether a given contextfree language is regular and whether two pushdown automata accept the same language.
Question 11 
Which of the following describes a handle (as applicable to LRparsing) appropriately?
It is the position in a sentential form where the next shift or reduce operation will occur.
 
It is nonterminal whose production will be used for reduction in the next step.  
It is a production that may be used for reduction in a future step along with a position in the sentential form where the next shift or reduce operation will occur.
 
It is the production p that will be used for reduction in the next step along with a position in the sentential form where the right hand side of the production may be found.

Question 11 Explanation:
A handle is the production p that will be used for reduction in the next step along with a position in the sentential form where the right hand side of the production may be found.
Question 12 
Some code optimizations are carried out on the intermediate code because
They enhance the portability of the compiler to other target processors
 
Program analysis is more accurate on intermediate code than on machine code
 
The information from dataflow analysis cannot otherwise be used for optimization  
The information from the front end cannot otherwise be used for optimization

Question 12 Explanation:
The codeoptimization on intermediate code generation will always enhance the portability of the compiler to target processors. The main reason behind this is, as the intermediate code is independent of the target processor on which the code will be executed, so the compiler is able to optimize the intermediate code more conveniently without bothering the underlying architecture of target processor.
Question 13 
regular  
contextfree  
contextsensitive  
recursive 
Question 13 Explanation:
If L is recursive enumerable, then it implies that there exist a Turing Machine (lets say M1) which always HALT for the strings which is in L.
If are recursively enumerable, then it implies that there exist a Turing Machine (lets say M2) which always HALT for the strings which is NOT in L(as L is complement of Since we can combine both Turing machines (M1 and M2) and obtain a new Turing Machine (say M3) which always HALT for the strings if it is in L and also if it is not in L. This implies that L must be recursive.
If are recursively enumerable, then it implies that there exist a Turing Machine (lets say M2) which always HALT for the strings which is NOT in L(as L is complement of Since we can combine both Turing machines (M1 and M2) and obtain a new Turing Machine (say M3) which always HALT for the strings if it is in L and also if it is not in L. This implies that L must be recursive.
Question 14 
What is the maximum size of data that the application layer can pass on to the TCP layer below?
Any size  
2^{16} bytessize of TCP header  
2^{16} bytes  
1500 bytes 
Question 14 Explanation:
Application Layer  Any size
Transport Layer  65515 byte
Network layer  65535 byte
Data link layer  1500 byte
Transport Layer  65515 byte
Network layer  65535 byte
Data link layer  1500 byte
Question 15 
I only  
II only  
III only  
III and IV only 
Question 15 Explanation:
Demorgan law:
∀xP(x)≡∼∃x(∼P(x))
∼∀x(∼P(x))≡∃x(P(x))
Given: ∀t ∈ r(P(t)) (1)
As per Demorgan law
(1) ⇒ ∼∃t ∈ r(∼P(t))
which is option (III).
∀xP(x)≡∼∃x(∼P(x))
∼∀x(∼P(x))≡∃x(P(x))
Given: ∀t ∈ r(P(t)) (1)
As per Demorgan law
(1) ⇒ ∼∃t ∈ r(∼P(t))
which is option (III).
Question 16 
A clustering index is defined on the fields which are of type
nonkey and ordering
 
nonkey and nonordering
 
key and ordering
 
key and nonordering

Question 16 Explanation:
Create index files, fields could be nonkey attributes and which are in ordered form so as to form clusters easily.
Question 17 
Which of the following system calls results in the sending of SYN packets?
socket  
bind
 
listen  
connect 
Question 17 Explanation:
When connect( ) is called by client, following three way handshake happens to establish the connection in TCP.
1) The client requests a connection by sending a SYN (synchronize) message to the server.
2) The server acknowledges this request by sending SYNACK back to the client.
3) The client responds with an ACK, and the connection is established.
1) The client requests a connection by sending a SYN (synchronize) message to the server.
2) The server acknowledges this request by sending SYNACK back to the client.
3) The client responds with an ACK, and the connection is established.
Question 18 
x = 3, y = 4, z = 2  
x = 6, y = 5, z = 3
 
x = 6, y = 3, z = 5
 
x = 5, y = 4, z = 5 
Question 18 Explanation:
Required final output value of a=4.
→ We can directly eliminate the options B & C, because none of the variable can assign a value 4.
→ Given explanation is
a=(x>y)?((x>z)?x:z):((y>z)?y:z)
Option A:
x=3; y=4; z=2
a=(3>4)?⇒No
Then evaluate second expression⇒(4>2)?Yes
⇒a=y
a=4 (True)
Option D:
x=5; y=4; z=5
a=(5>4)⇒Yes
Then evaluate first expression ⇒ (5>5)? No
⇒ a=z ⇒ a=5 (Not true)
⇒Answer is Option A.
→ We can directly eliminate the options B & C, because none of the variable can assign a value 4.
→ Given explanation is
a=(x>y)?((x>z)?x:z):((y>z)?y:z)
Option A:
x=3; y=4; z=2
a=(3>4)?⇒No
Then evaluate second expression⇒(4>2)?Yes
⇒a=y
a=4 (True)
Option D:
x=5; y=4; z=5
a=(5>4)⇒Yes
Then evaluate first expression ⇒ (5>5)? No
⇒ a=z ⇒ a=5 (Not true)
⇒Answer is Option A.
Question 19 
MNOPQR
 
NQMPOR
 
QMNPRO
 
QMNPOR 
Question 19 Explanation:
Check with the options:
Option A: MNOPQR
→ If queue starts with M then neighbour nodes are {N,Q,R}.
→If Q starts with M then string is not matching with neighbour nodes.
So, option A is wrong.
Option B: NQMPOR
→ Neighbours of N is ⇒ {Q,M,O}
String is not matched with neighbours.
So, option B is wrong.
Question 20 
The data blocks of a very large file in the Unix file system are allocated using
contiguous allocation
 
linked allocation
 
indexed allocation  
an extension of indexed allocation

Question 20 Explanation:
An Unix file system can utilizes an extension of indexed allocation. Because it uses direct blocks, single indirect blocks, double indirect blocks and triple indirect blocks.
Question 21 
1000e  
1000
 
100e  
100

Question 21 Explanation:
Trapezoidal rule error is En=(ba)^{3}/ 12N^{2} f''(c)
The given, Maximum error: 1/3×10^{6}
Then E_{n}<1/3×10^{6}
Upper bound b=z,
Lower bound a=1
⇒ Finally,
Answer is Option A.
The given, Maximum error: 1/3×10^{6}
Then E_{n}<1/3×10^{6}
Upper bound b=z,
Lower bound a=1
⇒ Finally,
Answer is Option A.
Question 22 
square of R
 
reciprocal of R  
square root of R
 
logarithm of R

Question 22 Explanation:
The given expression is
x_{n+1}=1/2(x_{n}+R/x_{n})
It can be written as
x_{n+1}=x_{n}((x_{n})^{2R)/2xn It computes square root R. Correct option is C.}
x_{n+1}=1/2(x_{n}+R/x_{n})
It can be written as
x_{n+1}=x_{n}((x_{n})^{2R)/2xn It computes square root R. Correct option is C.}
Question 23 
Which of the following statements is true for every planar graph on n vertices?
The graph is connected  
The graph is Eulerian
 
The graph has a vertexcover of size at most 3n/4
 
The graph has an independent set of size at least n/3

Question 23 Explanation:
Lets do with elimination method,
(A) Consider the following disconnected graph which is planar.
So false.
(B) A graph is Eulerian if all vertices have even degree but a planar graph can have vertices with odd degree.
So false.
(D) Consider K_{4} graph. It has independent set size 1 which is less than 4/3.
So false.
Hence, option (C) is correct.
(A) Consider the following disconnected graph which is planar.
So false.
(B) A graph is Eulerian if all vertices have even degree but a planar graph can have vertices with odd degree.
So false.
(D) Consider K_{4} graph. It has independent set size 1 which is less than 4/3.
So false.
Hence, option (C) is correct.
Question 24 
P = Q  k
 
P = Q + k  
P = Q
 
P = Q +2 k

Question 24 Explanation:
P=1+3+5+7+...+(2k1)
=(21)+(41)+(61)+(81)+...+(2k1)
=(2+4+6+8+...+2k)+(1+1+1+k times)
=Q(1+1+...+k times)
=Qk
Question 25 
A point on a curve is said to be an extremum if it is a local minimum or a local maximum. The number of distinct extrema for the curve 3x^{4}  16x^{3} + 24x^{2} + 37 is
0  
1  
2  
3 
Question 25 Explanation:
f(x)=3x^{4}16x^{3}+24x^{2}+37
f’(x)=12x^{3}+48x^{2}+48x=0 12x(x^{2}4x+4)=0 x=0; (x2)^{2}=0
x=2
f’’(x)=36x^{2}96x+48
f ”(0)=48
f ”(2)=36(4)96(2)+48
=144192+48
=0
At x=2, we can’t apply the second derivative test.
f’(1)=12; f’(3)=36, on either side of 2 there is no sign change then this is neither minimum or maximum.
Finally, we have only one Extremum i.e., x=0.
f’(x)=12x^{3}+48x^{2}+48x=0 12x(x^{2}4x+4)=0 x=0; (x2)^{2}=0
x=2
f’’(x)=36x^{2}96x+48
f ”(0)=48
f ”(2)=36(4)96(2)+48
=144192+48
=0
At x=2, we can’t apply the second derivative test.
f’(1)=12; f’(3)=36, on either side of 2 there is no sign change then this is neither minimum or maximum.
Finally, we have only one Extremum i.e., x=0.
Question 27 
Aishwarya studies either computer science or mathematics everyday. If she studies computer science on a day, then the probability that she studies mathematics the next day is 0.6. If she studies mathematics on a day, then the probability that she studies computer science the next day is 0.4. Given that Aishwarya studies computer science on Monday, what is the probability that she studies computer science on Wednesday?
0.24
 
0.36  
0.4  
0.6

Question 27 Explanation:
→ Aishwarya studied CS on Monday. Then we have two possibilities to she study computer science on wednesday.
(i) She study Mathematics on Tuesday and computer science on wednesday.
⇒ 0.6×0.4
⇒ 0.24
(ii) She study computer science on Tuesday and computer science on wednesday.
⇒ 0.4×0.4
⇒ 0.16
→ The probability that she study computer science on wednesday is
0.24+0.16=0.40
(i) She study Mathematics on Tuesday and computer science on wednesday.
⇒ 0.6×0.4
⇒ 0.24
(ii) She study computer science on Tuesday and computer science on wednesday.
⇒ 0.4×0.4
⇒ 0.16
→ The probability that she study computer science on wednesday is
0.24+0.16=0.40
Question 28 
one  
two  
three  
four 
Question 28 Explanation:
Answer: We have only one matrix with eigen value 1.
Question 29 
Let X be a random variable following normal distribution with mean +1 and variance 4. Let Y be another normal variable with mean 1 and variance unknown. If P(X ≤ 1) = P(Y ≥ 2), the standard deviation of Y is
3  
2  
√2  
1 
Question 29 Explanation:
P(X ≤ 1) = P(Y ≥ 2)
We can compare their values using standard normal distributions.
The above equation satisfies when σ_{y} will be equal to 3.
We can compare their values using standard normal distributions.
The above equation satisfies when σ_{y} will be equal to 3.
Question 30 
(∀x fsa(x)) ⇒ (∃y pda(y) ∧ equivalent(x,y))
 
∼∀y(∃x fsa(x) ⇒ pda(y) ∧ equivalent(x,y))  
∀x ∃y(fsa(x) ∧ pda(y) ∧ equivalent(x,y))
 
∀x ∃y(fsa(y)∧ pda(x) ∧ equivalent(x,y)) 
Question 30 Explanation:
Go through the options.
Option A:
If everything is a FSA. Then there exists an equivalent PDA for everything.
Option B:
Not for the case Y, if there exists a FSA then it can have equivalent PDA.
Option C:
Everything is a PDA and consists equivalent PDA.
Option D:
Everything is a PDA and has exist an equivalent FSA. In option A we are getting the equivalent of a and b.
So answer is option A.
Option A:
If everything is a FSA. Then there exists an equivalent PDA for everything.
Option B:
Not for the case Y, if there exists a FSA then it can have equivalent PDA.
Option C:
Everything is a PDA and consists equivalent PDA.
Option D:
Everything is a PDA and has exist an equivalent FSA. In option A we are getting the equivalent of a and b.
So answer is option A.
Question 31 
Only I and II
 
Only I, II and III  
Only I, II and IV
 
All of I, II, III and IV 
Question 31 Explanation:
I. P∨∼Q (✔️)
II. ∼(∼P∧Q)⇒(P∨∼Q)≡I (✔️)
III. (P×Q)∨(P×∼Q)∨(∼P×∼Q)
P∧(Q∨∼Q)∨(∼P∧∼Q)
P∨(∼P×∼Q)
(P∨∼P)×(P∨∼Q)
(P∨∼Q)≡I=II (✔️)
IV. (P×Q)∨(P∧∼Q)∨(∼P×Q)
P×(Q∨∼Q)∨(∼P∧Q)
P∨(∼P×Q)
(P∨∼P)×(P∨Q)
(P∨Q)≠I (❌)
So I≡II≡III (✔️)
II. ∼(∼P∧Q)⇒(P∨∼Q)≡I (✔️)
III. (P×Q)∨(P×∼Q)∨(∼P×∼Q)
P∧(Q∨∼Q)∨(∼P∧∼Q)
P∨(∼P×∼Q)
(P∨∼P)×(P∨∼Q)
(P∨∼Q)≡I=II (✔️)
IV. (P×Q)∨(P∧∼Q)∨(∼P×Q)
P×(Q∨∼Q)∨(∼P∧Q)
P∨(∼P×Q)
(P∨∼P)×(P∨Q)
(P∨Q)≠I (❌)
So I≡II≡III (✔️)
Question 32 
For a magnetic disk with concentric circular tracks, the seek latency is not linearly proportional to the seek distance due to
nonuniform distribution of requests
 
arm starting and stopping inertia  
higher capacity of tracks on the periphery of the platter  
use of unfair arm scheduling policies

Question 32 Explanation:
No such direct relation exists between latency and seek distance.
The order in which the sectors are read from disks has tremendous impact on performance. This is mainly because of seek time if request for sector are random.
So (d) is appropriate answer because it causes random access of sectors.
The order in which the sectors are read from disks has tremendous impact on performance. This is mainly because of seek time if request for sector are random.
So (d) is appropriate answer because it causes random access of sectors.
Question 33 
I only  
II only  
III Only
 
II and III only

Question 33 Explanation:
I : Self relocating code always takes some address in memory. So autoincrement mode is not used for self relocating code. Hence this statement is wrong.
II. An additional ALU is not necessary for autoincrement. So this statement is wrong.
III. In autoincrement addressing mode the address where next data block to be stored is generated automatically depending upon the size of single data item required to store. This is based on pointer arithmetic. So this statement is true.
Hence option C is the answer.
II. An additional ALU is not necessary for autoincrement. So this statement is wrong.
III. In autoincrement addressing mode the address where next data block to be stored is generated automatically depending upon the size of single data item required to store. This is based on pointer arithmetic. So this statement is true.
Hence option C is the answer.
Question 34 
I only  
II only  
I and II only
 
I, II and III only

Question 34 Explanation:
RFE is a privileged instruction that is performed explicitly by the Operating System to switch from kernel mode to user mode at the end of handling an exception. Hence it has to be a trap. We know when a trap/interrupt is in execution, till its completion all other trap/interrupts will not be allowed to execute. So option D is correct answer.
Question 35 
IV only  
I and IV only
 
I, III and IV only
 
I, II, III and IV

Question 35 Explanation:
Inclusion property: in this the presence of an address in a given level of the memory system guarantees that the address is present in all lower levels of the memory system.
1st is not always correct as data need not to be exactly same at the same point of time and so write back policy can be used in this instead of write through policy.
2nd is not needed when talking only about L1 and L2, as whether L2 is write through will have impact on any memory higher than L2, not on L1.
For 3rd, associativity can be equal also, so it need not be true.
For 4th statement, L2 cache has to be as large as L1 cache. In most cases L2 cache will be generally larger than L1 cache, but we will never have an L2 cache smaller than L1 cache. So only 4th statement is necessarily true. Hence option A is the answer.
1st is not always correct as data need not to be exactly same at the same point of time and so write back policy can be used in this instead of write through policy.
2nd is not needed when talking only about L1 and L2, as whether L2 is write through will have impact on any memory higher than L2, not on L1.
For 3rd, associativity can be equal also, so it need not be true.
For 4th statement, L2 cache has to be as large as L1 cache. In most cases L2 cache will be generally larger than L1 cache, but we will never have an L2 cache smaller than L1 cache. So only 4th statement is necessarily true. Hence option A is the answer.
Question 36 
I and II only
 
I and III only  
II and III only  
I, II and III 
Question 36 Explanation:
I  False Bypassing can't handle all RAW hazard, consider when any instruction depends on the result of LOAD instruction, now LOAD updates register value at Memory Access Stage (MA), so data will not be available directly on Execute stage.
II  True, register renaming can eliminate all WAR Hazard.
III If the 3rd statement says "Control hazard penalties can be completely eliminated by dynamic branch prediction", then it is false, but it is only given that "Control hazard penalties can be eliminated by dynamic branch prediction". So we can't say that this statement is false. In all the given options we don't have any option which says only statement I is false, so the next better choice is considering both statements I and III as false. Hence option B is the answer.
II  True, register renaming can eliminate all WAR Hazard.
III If the 3rd statement says "Control hazard penalties can be completely eliminated by dynamic branch prediction", then it is false, but it is only given that "Control hazard penalties can be eliminated by dynamic branch prediction". So we can't say that this statement is false. In all the given options we don't have any option which says only statement I is false, so the next better choice is considering both statements I and III as false. Hence option B is the answer.
Question 37 
I only
 
II only  
III only  
I, II and III

Question 37 Explanation:
I is true because when we make a function call there are some input registers and some output registers. If function F() is calling function G(), we can make the caller function F()'s output registers the same as the called procedure G()'s input registers this is done using overlapping register windows.This will reduce the memory accesses so that F()'s output need not be put into memory for G() to access again from memory.
II is false as register saves and restores would still be required for each and every variable.
III is also false as instruction fetch is not affected by memory access using multiple register windows.
II is false as register saves and restores would still be required for each and every variable.
III is also false as instruction fetch is not affected by memory access using multiple register windows.
Question 38 
In an instruction execution pipeline, the earliest that the data TLB (Translation Lookaside Buffer) can be accessed is
Before effective address calculation has started
 
During effective address calculation  
After effective address calculation has completed  
After data cache lookup has completed 
Question 38 Explanation:
TLB is a mini page table and it contains the frequently accessed page table entries. Because logical address is effective address, only after we calculate what is the effective address we can access the TLB. Hence option C is the correct answer.
Question 39 
f(n) = O(g(n)); g(n) = O(h(n))
 
f(n) = Ω(g(n)); g(n) = O(h(n))
 
g(n) = O(f(n)); h(n) = O(f(n))  
h(n) = O(f(n)); g(n) = Ω(f(n))

Question 39 Explanation:
When we want to find asymptotically bigger/smaller functions, we have to follow basically 2 steps:
1. Check whether the function if polynomial time or exponential time.
2. Group them into polynomial functions and exponential function. The exponential functions are always bigger than polynomial functions.
As per the above 3 functions, the g(n) is greater than others. f(n) greater than h(n). So, the order of growth h(n) < f(n) < g(n).
Note: For computing, take always big number.
1. Check whether the function if polynomial time or exponential time.
2. Group them into polynomial functions and exponential function. The exponential functions are always bigger than polynomial functions.
As per the above 3 functions, the g(n) is greater than others. f(n) greater than h(n). So, the order of growth h(n) < f(n) < g(n).
Note: For computing, take always big number.
Question 40 
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is
θ(n)
 
θ(logn)  
θ(log*n)  
θ(1) 
Question 40 Explanation:
The Best way to find out whether an integer appears more than n/2 times in a sorted array(Ascending Order) of n integers, would be binary search approach.
1. The First occurrence of an element can be found out in O(log(n))time using divide and conquer technique,lets say it is i.
2. The Last occurrence of an element can be found out in O(log(n)) time using divide and conquer technique,lets say it is j.
3. Now number of occurrence of that element(count) is (ji+1).
Overall time complexity = log n +log n +1 = O(logn)
Program:
/* If x is present in arr[low...high] then returns the index of first occurrence of x, otherwise returns 1 */
int binarySearch(int arr[], int low, int high, int x){
if (high >= low) {
int mid = (low + high)/2; /*low + (high  low)/2;*/
/* Check if arr[mid] is the first occurrence of x.
arr[mid] is first occurrence if x is one of the following is true:
(i) mid == 0 and arr[mid] == x
(ii) arr[mid1] < x and arr[mid] == x */
if ( (mid == 0  x > arr[mid1]) && (arr[mid] == x) )
return mid;
else if (x > arr[mid]
) return _binarySearch(arr, (mid + 1), high, x);
else
return _binarySearch(arr, low, (mid 1), x);
}
return 1;
}
Note: The code finds out the first occurrence of the element in the array and checks if the element at (n/2+1)th position is same(as the array is sorted). Takes O(logn) time.
1. The First occurrence of an element can be found out in O(log(n))time using divide and conquer technique,lets say it is i.
2. The Last occurrence of an element can be found out in O(log(n)) time using divide and conquer technique,lets say it is j.
3. Now number of occurrence of that element(count) is (ji+1).
Overall time complexity = log n +log n +1 = O(logn)
Program:
/* If x is present in arr[low...high] then returns the index of first occurrence of x, otherwise returns 1 */
int binarySearch(int arr[], int low, int high, int x){
if (high >= low) {
int mid = (low + high)/2; /*low + (high  low)/2;*/
/* Check if arr[mid] is the first occurrence of x.
arr[mid] is first occurrence if x is one of the following is true:
(i) mid == 0 and arr[mid] == x
(ii) arr[mid1] < x and arr[mid] == x */
if ( (mid == 0  x > arr[mid1]) && (arr[mid] == x) )
return mid;
else if (x > arr[mid]
) return _binarySearch(arr, (mid + 1), high, x);
else
return _binarySearch(arr, low, (mid 1), x);
}
return 1;
}
Note: The code finds out the first occurrence of the element in the array and checks if the element at (n/2+1)th position is same(as the array is sorted). Takes O(logn) time.
Question 41 
A Btree of order 4 is built from scratch by 10 successive insertions. What is the maximum number of node splitting operations that may take place?
3  
4  
5  
6 
Question 41 Explanation:
Let's take 10 successive key values,
{1,2,3,...,10} which can cause maximum possi ble splits.
1, 2, 3 →
4 →
5 →
6 →
7 →
8 →
9 →
10 →
{1,2,3,...,10} which can cause maximum possi ble splits.
1, 2, 3 →
4 →
5 →
6 →
7 →
8 →
9 →
10 →
Question 42 
G is a graph on n vertices and 2n – 2 edges. The edges of G can be partitioned into two edgedisjoint spanning trees. Which of the following is NOT true for G?
For every subset of k vertices, the induced subgraph has at most 2k–2 edges  
The minimum cut in G has at least two edges
 
There are two edgedisjoint paths between every pair to vertices
 
There are two vertexdisjoint paths between every pair of vertices 
Question 42 Explanation:
→ In Spanning tree n nodes require n1 edges. The above question they mentioned 2 disjoint spanning trees. So, it requires n1 + n1 =2n2 edges. Except option D everything is correct.
> Option A: True: Subgraph with k vertices here is no chance to get more than 2k−2 edges. Subgraph with n−k vertices, definitely less than 2n−2k edges.
> Option B: True: Take any subgraph SG with k vertices. The remaining subgraph will have n−k vertices. Between these two subgraphs there should be at least 2 edges because we are taken 2 spanning trees in SG.
> Option C: True: A spanning tree covers all the vertices. So, 2 edgedisjoint spanning trees in G means, between every pair of vertices in G we have two edgedisjoint paths (length of paths may vary).
> Option A: True: Subgraph with k vertices here is no chance to get more than 2k−2 edges. Subgraph with n−k vertices, definitely less than 2n−2k edges.
> Option B: True: Take any subgraph SG with k vertices. The remaining subgraph will have n−k vertices. Between these two subgraphs there should be at least 2 edges because we are taken 2 spanning trees in SG.
> Option C: True: A spanning tree covers all the vertices. So, 2 edgedisjoint spanning trees in G means, between every pair of vertices in G we have two edgedisjoint paths (length of paths may vary).
Question 43 
Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sublists each of which contains at least onefifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then
T(n) ≤ 2T(n/5) + n
 
T(n) ≤ T(n/5) + T(4n/5) + n
 
T(n) ≤ 2T(4n/5) + n  
T(n) ≤ 2T(n/2) + n

Question 43 Explanation:
For the case where n/5 elements are in one subset, T(n/5) comparisons are needed for the first subset with n/5 elements, T(4n/5) is for the rest 4n/5 elements, and n is for finding the pivot. If there are more than n/5 elements in one set then other set will have less than 4n/5 elements and time complexity will be less than T(n/5) + T(4n/5) + n because recursion tree will be more balanced.
Question 44 
Q solves the subsetsum problem in polynomial time when the input is encoded in unary
 
Q solves the subsetsum problem in polynomial time when the input is encoded in binary
 
The subset sum problem belongs to the class NP  
The subset sum problem is NPhard

Question 44 Explanation:
Suppose the input is encoded in binary format. If W is an exponential in terms of the input length of W and O(nW) also becomes exponential in terms of the input lengths. Q is not a polynomial time algorithm.
Note: As per Present GATE syllabus , the above concept is not required.
Note: As per Present GATE syllabus , the above concept is not required.
Question 45 
only vertex a  
only vertices a, e, f, g, h
 
only vertices a, b, c, d
 
all the vertices 
Question 45 Explanation:
The single source shortest path algorithm(Dijkstra’s) is not work correctly for negative edge weights and negative weight cycle. But as per the above graph it works correct. It gives from shortest path between ‘a’ vertex to all other vertex. The Dijkstra’s algorithm will follow greedy strategy.
AB ⇒ 1
AC⇒ 1+2=3
AE⇒ 13 =2
AF⇒ 1 3 +2 =0
AG⇒ 1 3 +2 +3 =3
AC ⇒1 +2 =3
AH⇒ 1+2 5 =2
AB ⇒ 1
AC⇒ 1+2=3
AE⇒ 13 =2
AF⇒ 1 3 +2 =0
AG⇒ 1 3 +2 +3 =3
AC ⇒1 +2 =3
AH⇒ 1+2 5 =2
Question 46 
You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2, ..., n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?
θ(log n)
 
θ(n)  
θ(nlog n)
 
None of the above, as the tree cannot be uniquely determined

Question 46 Explanation:
Last element in post order is the root of tree find this element in inorderlog n time. Now as in quick sort consider this as pivot and split the post order array into 2. All elements smaller than pivot goes to left and all elements larger than pivot goes to right and suppose we have k elements smaller than pivot, these elements will be same in both inorder as well as post order. Now, we already got the root, now left child is the left split and right child is the right split.
T(n) = T(k) + T(nk1) + logn
In worst case T(n) = O(nlogn), when k=0
But searching for an element in the inorder traversal of given BST can be done in O(1) because we have n elements from 1...n so there is no need to search an element if last element in post order is say 5 we take it as root and since 4 elements are split the post order array into two (first 4 elements), (6th element onward) and solve recursively. Time complexity for this would be
T(n) = T(k) + T(nk1)+O(1)
Which gives T(n) = O(n)
since we know that all elements must be traversed at least once T(n) = θ(n)
T(n) = T(k) + T(nk1) + logn
In worst case T(n) = O(nlogn), when k=0
But searching for an element in the inorder traversal of given BST can be done in O(1) because we have n elements from 1...n so there is no need to search an element if last element in post order is say 5 we take it as root and since 4 elements are split the post order array into two (first 4 elements), (6th element onward) and solve recursively. Time complexity for this would be
T(n) = T(k) + T(nk1)+O(1)
Which gives T(n) = O(n)
since we know that all elements must be traversed at least once T(n) = θ(n)
Question 47 
We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is
θ(log n)  
θ(n)  
θ(nlog n)
 
θ(n^{2})

Question 47 Explanation:
Inserting an element into binary(either max or min) heap takes O(logn) for all cases, but in question they clearly mentioned that n elements and inserting one by one n elements, so it takes 2n time. So, O(n).
Note: We can also insert all the elements once, there will be no difference on time complexity.
Note: We can also insert all the elements once, there will be no difference on time complexity.
Question 48 
Which of the following statements is false?
Every NFA can be converted to an equivalent DFA  
Every nondeterministic Turing machine can be converted to an equivalent deterministic Turing machine
 
Every regular language is also a contextfree language
 
Every subset of a recursively enumerable set is recursive 
Question 48 Explanation:
Every NFA can be converted into DFA (as there exist a standard procedure to convert NFA into DFA). Also, every nondeterministic Turing machine can be converted to an equivalent deterministic Turing machine. Every regular language is also a CFL , since if a language can be recognized by Finite automata, then it must also be recognize by PDA (as PDA is more powerful than FA). But every subset of recursively enumerable need not be recursive.
Question 49 
Question 49 Explanation:
The product automata will have states {11, 12, 21, 22} and “11” is inItial state and “22” is final state. By comparison we can easily infer that state {11, 12, 21, 22} is renamed as {P, Q, S, R}, wheresP is initial state (state “11”) and R is final state (state “22”).
Lets rename table Z (for sake of clarity)
And Table Y (same as given in question)
The product automata will have states { One1, One2, Two1, Two2} Where One1 is P , Two2 is R and One2 is Q and Two1 is S.
The transition table for Z × Y is given below:
NOTE: LAST TWO ROWS DOESN’T MATCH WITH OPTION A. BUT IF THE ASSUMPTION IN QUESTION SUCH AS STATE “11” IS P AND STATE “22” IS R, HOLDS, THEN THE ONLY OPTION MATCHES WITH PRODUCT AUTOMATA IS OPTION A, AS (FIRST ROW) , P (ON “a”) > S AND P (ON “b”) > R, IS THE ONLY OPTION MATCHING WITH OPTION A.
Lets rename table Z (for sake of clarity)
And Table Y (same as given in question)
The product automata will have states { One1, One2, Two1, Two2} Where One1 is P , Two2 is R and One2 is Q and Two1 is S.
The transition table for Z × Y is given below:
NOTE: LAST TWO ROWS DOESN’T MATCH WITH OPTION A. BUT IF THE ASSUMPTION IN QUESTION SUCH AS STATE “11” IS P AND STATE “22” IS R, HOLDS, THEN THE ONLY OPTION MATCHES WITH PRODUCT AUTOMATA IS OPTION A, AS (FIRST ROW) , P (ON “a”) > S AND P (ON “b”) > R, IS THE ONLY OPTION MATCHING WITH OPTION A.
Question 50 
I, II, III and IV  
II, III and IV only  
I, III and IV only  
I, II and IV only 
Question 50 Explanation:
Every left recursive grammar can be converted to a rightrecursive grammar and viceversa, the conversion of a left recursive grammar into right recursive is also known as eliminating left recursion from the grammar. Statement III is also true, as this is the standard definition of regular grammar (TYPE 3 grammar). Statement IV is also true, as in CNF the only productions allowed are of type:
A> BC
A> a // where “a” is any terminal and B, C are any variables.
When we draw the parse tree for the grammar in CNF, it will always have at most two childs in every step, so it always results binary tree.
But statement II is false, as if the language contains empty string then we cannot remove every epsilon production from the CFG, since at least one production (mainly S → ϵ) must be there in order to derive empty string in language.
A> BC
A> a // where “a” is any terminal and B, C are any variables.
When we draw the parse tree for the grammar in CNF, it will always have at most two childs in every step, so it always results binary tree.
But statement II is false, as if the language contains empty string then we cannot remove every epsilon production from the CFG, since at least one production (mainly S → ϵ) must be there in order to derive empty string in language.
Question 51 
E  P, F  R, G  Q, H  S  
E  R, F  P, G  S, H  Q  
E  R, F  P, G  Q, H  S
 
E  P, F  R, G  S, H  Q

Question 51 Explanation:
The grammar in S {X →bXb  cXc  ϵ} derives all even length Palindromes, So H matches with S.
F matches with P, Number of formal parameters in the declaration…. matches with {L={ a^{n} b^{m} c ^{n} d^{m}  m,n >=1}
Since, a^{n} b^{m} corresponds to formal parameter (if n=2 and m=1, and “a” is int type and “b”is float type, then it means (int,int,float)) and c^{n} d^{m} corresponds to actual parameter used in function.
Similarly other two can also be argued by their reasons, but with F matches with P and H matches with S implies that option C is the only correct option.
F matches with P, Number of formal parameters in the declaration…. matches with {L={ a^{n} b^{m} c ^{n} d^{m}  m,n >=1}
Since, a^{n} b^{m} corresponds to formal parameter (if n=2 and m=1, and “a” is int type and “b”is float type, then it means (int,int,float)) and c^{n} d^{m} corresponds to actual parameter used in function.
Similarly other two can also be argued by their reasons, but with F matches with P and H matches with S implies that option C is the only correct option.
Question 52 
P2, Q1, R3, S4
 
P1, Q3, R2, S4
 
P1, Q2, R3, S4  
P3, Q2, R1, S4 
Question 52 Explanation:
The NFA represented by P, accepts string “00” and then at final state (other than initial state) we have self loop of “1” , so we conclude that it must accept the string of the form of > ϵ + 0 X* 01*, where X is regular expression (01*1 + 00 ) {resolving the loop at middle state}. It matches with statement 1.
Similarly, The NFA represented by Q, has the form of > ϵ + 0X*0, where X is regular expression (10*1 + 00 ) {resolving the loop at middle state}. It matches with statement 2.
The NFA represented by R, has the form of > ϵ + 0X*1, where X is regular expression (10*1 + 01 ) {resolving the loop at middle state}. It matches with statement 3.
The NFA represented by S, accepts string “01” and then at final state (other than initial state) we have self loop of “0” , so we conclude that it must accept the string of the form of > ϵ + 0X* 10*, where X is regular expression (10*1 + 10 ) {resolving the loop at middle state}. It matches with statement 4.
Similarly, The NFA represented by Q, has the form of > ϵ + 0X*0, where X is regular expression (10*1 + 00 ) {resolving the loop at middle state}. It matches with statement 2.
The NFA represented by R, has the form of > ϵ + 0X*1, where X is regular expression (10*1 + 01 ) {resolving the loop at middle state}. It matches with statement 3.
The NFA represented by S, accepts string “01” and then at final state (other than initial state) we have self loop of “0” , so we conclude that it must accept the string of the form of > ϵ + 0X* 10*, where X is regular expression (10*1 + 10 ) {resolving the loop at middle state}. It matches with statement 4.
Question 53 
I and IV only  
I and III only  
I only
 
IV only 
Question 53 Explanation:
Statement I represents a regular language whose regular expression is a* (bb)*. Also it doesn’t require any comparison between “a” and “b” , so it can be recognized by DFA and hence regular.
Statement II and III represent CFL, as it requires comparison between number of a’s and b’s.
Statement IV is also regular, and its regular expression is (a+b)* c (a+b)*.
Statement II and III represent CFL, as it requires comparison between number of a’s and b’s.
Statement IV is also regular, and its regular expression is (a+b)* c (a+b)*.
Question 54 
II and V only  
I, III and IV only
 
I, II and V only
 
II, III and V only 
Question 54 Explanation:
II. Multilevel access link (or display) arrangement is needed to arrange Activation Records only if the programming language being implemented has nesting of procedures and functions.
V. PL’s which permits a function to return a function as its result cannot be implemented with a stackbased storage allocation scheme for activation records.
II & V are True.
V. PL’s which permits a function to return a function as its result cannot be implemented with a stackbased storage allocation scheme for activation records.
II & V are True.
Question 55 
An LALR(1) parser for a grammar G can have shiftreduce (SR) conflicts if and only if
the SLR(1) parser for G has SR conflicts
 
the LR(1) parser for G has SR conflicts
 
the LR(0) parser for G has SR conflicts  
the LALR(1) parser for G has reducereduce conflicts

Question 55 Explanation:
LALR(1) parser is obtained by minimising the LR(1) parser and hence they both uses LR(1) items. Now consider if LR(1) parser has SR conflict, for ex:
Consider a state in LR(1) parser:
S> x.yA, a
A> x. , y
This has both shift and reduce conflict on symbol “y”.
Since LR(1) already has SR conflict , so resulting LALR(1) (after merging) will also have SR conflict.
Now if LR(1) doesn’t have SR conflict then it is guaranteed that the LALR(1) will never have SR conflict. The reason behind this is, as we merge those state only which has same set of canonical items except look ahead and the LR(1) canonical items has DFA (means from one state to other state the transition is from unique symbol) , so after merging also we will never see any shift conflict, only reducereduce may occur.
Hence An LALR(1) parser for a grammar G can have shiftreduce (SR) conflicts if and only if the LR(1) parser for G has SR conflicts.
Consider a state in LR(1) parser:
S> x.yA, a
A> x. , y
This has both shift and reduce conflict on symbol “y”.
Since LR(1) already has SR conflict , so resulting LALR(1) (after merging) will also have SR conflict.
Now if LR(1) doesn’t have SR conflict then it is guaranteed that the LALR(1) will never have SR conflict. The reason behind this is, as we merge those state only which has same set of canonical items except look ahead and the LR(1) canonical items has DFA (means from one state to other state the transition is from unique symbol) , so after merging also we will never see any shift conflict, only reducereduce may occur.
Hence An LALR(1) parser for a grammar G can have shiftreduce (SR) conflicts if and only if the LR(1) parser for G has SR conflicts.
Question 56 
In the slow start phase of the TCP congestion control algorithm, the size of the congestion window
does not increase
 
increases linearly  
increases quadratically
 
increases exponentially

Question 56 Explanation:
In slow start phase, window size will grow exponentially. when the threshold is reached and congestion avoidance phase begins. In congestion avoidance phase, the window is increased linearly.
Question 57 
If a class B network on the Internet has a subnet mask of 255.255.248.0, what is the maximum number of hosts per subnet?
1022
 
1023
 
2046
 
2047 
Question 57 Explanation:
255.255.248.0 can be written as 11111111.11111111.11111000.00000000
Number of bits assigned for host id is the number of zeros in subnet mask. Here 11 bits are used.
for host id so maximum possible hosts are= 2^{11} 2=2046
Number of bits assigned for host id is the number of zeros in subnet mask. Here 11 bits are used.
for host id so maximum possible hosts are= 2^{11} 2=2046
Question 58 
A computer on a 10Mbps network is regulated by a token bucket. The token bucket is filled at a rate of 2Mbps. It is initially filled to capacity with 16Megabits. What is the maximum duration for which the computer can transmit at the full 10Mbps?
1.6 seconds  
2 seconds  
5 seconds
 
8 seconds 
Question 58 Explanation:
Duration = C/xy, where C is the initial capacity, x is outgoing rate and y is incoming rate.
Question 59 
A client process P needs to make a TCP connection to a server process S. Consider the following situation: the server process S executes a socket (), a bind () and a listen () system call in that order, following which it is preempted. Subsequently, the client process P executes a socket () system call followed by connect () system call to connect to the server process S. The server process has not executed any accept() system call. Which one of the following events could take place?
connect ( ) system call returns successfully
 
connect ( ) system call blocks
 
connect ( ) system call returns an error
 
connect ( ) system call results in a core dump

Question 59 Explanation:
Connect() System call is not blocking system call but it blocks until connection is established or rejected. If accept() is not executed at server then connection will be rejected and an error statement is returned.
Question 60 
18  
19  
21  
22 
Question 60 Explanation:
f(c,b,a)
f(c,&c,&(&c))=f(4,4,4)
c is 4, b is a pointer pointing address of a, a is a pointer to pointer of c. Hence both b and c are pointing to same memory address i.e., a.
Hence whatever increment operation happens in f, it happens/ reflects on same value i.e., a.
**ppz+=1;
z=**ppz; //z=5
These steps update it to 5 and stored in z.
*py+=2; //changes c to 7, x is unchanged.
y=*py; //y=7
It updates to 7 and stored in y.
x+=3 //x is incremented by 3.
returns x+y+z=7+7+5=19
f(c,&c,&(&c))=f(4,4,4)
c is 4, b is a pointer pointing address of a, a is a pointer to pointer of c. Hence both b and c are pointing to same memory address i.e., a.
Hence whatever increment operation happens in f, it happens/ reflects on same value i.e., a.
**ppz+=1;
z=**ppz; //z=5
These steps update it to 5 and stored in z.
*py+=2; //changes c to 7, x is unchanged.
y=*py; //y=7
It updates to 7 and stored in y.
x+=3 //x is incremented by 3.
returns x+y+z=7+7+5=19
Question 61 
?1 is (getchar( ) != ’\n’) ?2 is getchar(c);  
?1 is (c = getchar( ) ) != ’\n’) ?2 is getchar(c);  
?1 is (c != ’\n’) ?2 is putchar(c);  
?1 is ((c = getchar()) != ’\n’) ?2 is putchar(c); 
Question 61 Explanation:
void reverse(void)
{
int c;
if(?1) reverse( );
?2
}
main( )
{
printf(“Enter Text”);
printf(“\n”);
reverse( );
printf(“\n”);
}
We can simply eliminate A & B for ?2.
& Hence
?1 is ((c=getchar( )) != ‘\n’)
?2 is putchar(c);
{
int c;
if(?1) reverse( );
?2
}
main( )
{
printf(“Enter Text”);
printf(“\n”);
reverse( );
printf(“\n”);
}
We can simply eliminate A & B for ?2.
& Hence
?1 is ((c=getchar( )) != ‘\n’)
?2 is putchar(c);
Question 62 
1,2,3,4,5,6,7  
2,1,4,3,6,5,7  
1,3,2,5,4,7,6  
2,3,4,5,6,7,1

Question 62 Explanation:
The given list is 1,2,3,4,5,6,7.
After 1st Iteration: 2,1,3,4,5,6,7
2nd Iteration: 2,1,4,3,5,6,7
3rd Iteration: 2,1,4,3,6,5,7
After each exchange is done, it starts from unchanged elements due to p=q⟶next;
‘p’ pointing to Null & q pointing to 7.
Hence 2,1,4,3,6,5,7.
After 1st Iteration: 2,1,3,4,5,6,7
2nd Iteration: 2,1,4,3,5,6,7
3rd Iteration: 2,1,4,3,6,5,7
After each exchange is done, it starts from unchanged elements due to p=q⟶next;
‘p’ pointing to Null & q pointing to 7.
Hence 2,1,4,3,6,5,7.
Question 63 
0 and 0
 
0 and 1  
1 and 0  
1 and 1 
Question 63 Explanation:
x_{b} must be 1 because both P(s) operation and V(s) operation perform P_{b}(x_{b}) first. So if x_{b}=0, then all the process performing these operations will be blocked.
Y_{b} must be '0' initially, because if Y_{b} is '1' initially then two process can be in critical section at the same time.
So answer is Option (C).
Y_{b} must be '0' initially, because if Y_{b} is '1' initially then two process can be in critical section at the same time.
So answer is Option (C).
Question 64 
Which of the following statements about synchronous and asynchronous I/O is NOT true?
An ISR is invoked on completion of I/O in synchronous I/O but not in asynchronous I/O
 
In both synchronous and asynchronous I/O, an ISR (Interrupt Service Routine) is invoked after completion of the I/O
 
A process making a synchronous I/O call waits until I/O is complete, but a process making an asynchronous I/O call does not wait for completion of the I/O
 
In the case of synchronous I/O, the process waiting for the completion of I/O is woken up by the ISR that is invoked after the completion of I/O

Question 64 Explanation:
Synchronous I/O mean that some flow of execution (such as a process or thread) is waiting for the operation to complete. Asynchronous I/O means that nothing is waiting for the operation to complete and the completion of the operation itself causes something to happen.
Synchronous I/O  some execution vehicle (like a process or thread) that initiates the I/O also waits for the I/O to complete (and perhaps completes it). When the I/O completes, that same execution vehicle goes on to do something else, perhaps using the results of the I/O.
Asynchronous I/O  no execution vehicle waits for the I/O to complete. When the I/O completes, whatever execution vehicle happens to complete the I/O may arrange for later things to happen.
Option B is not true, because both synchronous and asynchronous I/O, an ISR (Interrupt Service Routine) is not invoked after completion of the I/O.
Synchronous I/O  some execution vehicle (like a process or thread) that initiates the I/O also waits for the I/O to complete (and perhaps completes it). When the I/O completes, that same execution vehicle goes on to do something else, perhaps using the results of the I/O.
Asynchronous I/O  no execution vehicle waits for the I/O to complete. When the I/O completes, whatever execution vehicle happens to complete the I/O may arrange for later things to happen.
Option B is not true, because both synchronous and asynchronous I/O, an ISR (Interrupt Service Routine) is not invoked after completion of the I/O.
Question 65 
Which of the following is NOT true of deadlock prevention and deadlock avoidance schemes?
In deadlock prevention, the request for resources is always granted if the resulting state is safe
 
In deadlock avoidance, the request for resources is always granted if the result state is safe  
Deadlock avoidance is less restrictive than deadlock prevention  
Deadlock avoidance requires knowledge of resource requirements a priori

Question 65 Explanation:
Deadlock prevention scheme handles deadlock by making sure that one of the four necessary conditions don't occur. So, it may be the case that a resource request might be rejected even if the resulting state is safe. Hence, option (A) is false.
Question 66 
n  
(2^{n})  1
 
2^{n}  
(2^{n+1})  1

Question 66 Explanation:
Fork is a system call, implements in kernel.
It is a operation where process creates a copy of itself.
1,3,7,15,31,... ⇒ 2^{n}1
It is a operation where process creates a copy of itself.
1,3,7,15,31,... ⇒ 2^{n}1
Question 67 
20, 20 and 20
 
24, 24 and 24
 
24, 24 and 20
 
25, 25 and 24

Question 67 Explanation:
Virtual address size = 32 bits
From the question we can see the below info:
Physical address size = 36 bits
Physical memory size = 2^{36} bytes
Page frame size = 4K bytes = 2^{12} bytes
No. of bits for offset = 12
No. of bits required to access physical memory frame = 36 – 12 = 24
So in third level of page table, 24 bits are required to access an entry.
In second level page table entry  9 bits of virtual address are used to access second level page table entry and size of pages in second level is 4 bytes.
So size of second level page table is (2^{9})*4 = 2^{11} bytes. It means there are (2^{36})/(2^{11}) possible locations to store this page table. Therefore the second page table requires 25 bits to address it. the first page table needs 25 bits.
Answer  D
First level
From the question we can see the below info:
Physical address size = 36 bits
Physical memory size = 2^{36} bytes
Page frame size = 4K bytes = 2^{12} bytes
No. of bits for offset = 12
No. of bits required to access physical memory frame = 36 – 12 = 24
So in third level of page table, 24 bits are required to access an entry.
In second level page table entry  9 bits of virtual address are used to access second level page table entry and size of pages in second level is 4 bytes.
So size of second level page table is (2^{9})*4 = 2^{11} bytes. It means there are (2^{36})/(2^{11}) possible locations to store this page table. Therefore the second page table requires 25 bits to address it. the first page table needs 25 bits.
Answer  D
First level
Question 68 
Only I and II
 
Only I and III
 
Only I, II and III  
Only I, III and IV 
Question 68 Explanation:
Natural join is based on the common columns of the two tables.
We have two common columns in 'R' and 'S' which are 'P' and 'Q'.
(I) Both P and Q are used while doing the join, i.e., both P and Q are used to filter.
(II) Q is not used here for filtering. Natural join is done on all P's from R and all P's from S. So different from option (I).
(III) Through venn diagram it can be proved that A∩B = A  (AB).
So through above formula we can say that (III) and (IV) are equivalent.
So finally (I), (III) and (IV) are equivalent.
We have two common columns in 'R' and 'S' which are 'P' and 'Q'.
(I) Both P and Q are used while doing the join, i.e., both P and Q are used to filter.
(II) Q is not used here for filtering. Natural join is done on all P's from R and all P's from S. So different from option (I).
(III) Through venn diagram it can be proved that A∩B = A  (AB).
So through above formula we can say that (III) and (IV) are equivalent.
So finally (I), (III) and (IV) are equivalent.
Question 69 
Both Book and Collection are in BCNF
 
Both Book and Collection are in 3NF only
 
Book is in 2NF and Collection is in 3NF
 
Both Book and Collection are in 2NF only

Question 69 Explanation:
Given that
Book(Title, Author, Catalog_no, Publisher, Year, Price)
Collection(Title, Author, Catalog_no)
I) Title Author ⟶ Catalog_no ⟶ BCNR
II) Catalog_no ⟶ Title, Author, Publisher, Year ⟶ 3NF
III) Publisher Title Year ⟶Price ⟶ 2NF Book’s in 2NF
Collection is in 3NF.
Book(Title, Author, Catalog_no, Publisher, Year, Price)
Collection(Title, Author, Catalog_no)
I) Title Author ⟶ Catalog_no ⟶ BCNR
II) Catalog_no ⟶ Title, Author, Publisher, Year ⟶ 3NF
III) Publisher Title Year ⟶Price ⟶ 2NF Book’s in 2NF
Collection is in 3NF.
Question 70 
Consider a file of 16384 records. Each record is 32 bytes long and its key field is of size 6 bytes. The file is ordered on a nonkey field, and the file organization is unspanned. The file is stored in a file system with block size 1024 bytes, and the size of a block pointer is 10 bytes. If the secondary index is built on the key field of the file, and a multilevel index scheme is used to store the secondary index, the number of firstlevel and secondlevel blocks in the multilevel index are respectively
8 and 0  
128 and 6  
256 and 4
 
512 and 5 
Question 70 Explanation:
Total no. of records in a file = 16384
Record size = 32 bytes
Key size = 6 bytes
Block pointer size = 10 bytes
Block size of file system = 1024 bytes
Record (or) index entry size = 10+6 = 16 bytes
In first level no. of blocks =No. of records in a file/Block size=16384 * 16/1024=256
In second level, it have = 256*16 entries
In second level, no. of blocks =No. of entries/Block size =256*16/1024=4
Record size = 32 bytes
Key size = 6 bytes
Block pointer size = 10 bytes
Block size of file system = 1024 bytes
Record (or) index entry size = 10+6 = 16 bytes
In first level no. of blocks =No. of records in a file/Block size=16384 * 16/1024=256
In second level, it have = 256*16 entries
In second level, no. of blocks =No. of entries/Block size =256*16/1024=4
Question 71 
32Kbits  
34Kbits  
64Kbits  
68Kbits

Question 71 Explanation:
It is given that cache size = 64KB
Block size = 16 Bytes = 2^{4} Bytes, so block offset = 4 bits
Number of blocks in the cache = 64KB / 16B = 4K
It is 2way set associative cache, so each set contains 2 blocks.
So, number of sets = 4K / 2 = 2K = 2^{11}
So, we need 11bits for set indexing.
Since the address is 32 bits long, number of tag bits = 32−11−4 = 17
Total size of the tag directory = No. of tag bits ×Number of cache blocks =17×4K
=68 Kbits
Block size = 16 Bytes = 2^{4} Bytes, so block offset = 4 bits
Number of blocks in the cache = 64KB / 16B = 4K
It is 2way set associative cache, so each set contains 2 blocks.
So, number of sets = 4K / 2 = 2K = 2^{11}
So, we need 11bits for set indexing.
Since the address is 32 bits long, number of tag bits = 32−11−4 = 17
Total size of the tag directory = No. of tag bits ×Number of cache blocks =17×4K
=68 Kbits
Question 72 
ARR [0] [4]  
ARR [4] [0]
 
ARR [0] [5]  
ARR [5] [0]

Question 72 Explanation:
It is given that cache size = 64KB
Block size = 16 Bytes
Number of blocks in the cache = 64KB / 16B = 4K
It is 2way set associative cache, so each set contains 2 blocks.
So, number of sets = 4K / 2 = 2K = 2^{11}
Each element size = 8B and size of each block = 16 B
No. of elements in one block = 16/8 = 2 We know no. of elements in one row of the array = 1024. So, no. of blocks for one row of the array = 1024/2 = 512
We know there are 2^{11} sets, and each set has two blocks.
For any element to share the same cache index as ARR[0][0], it has to belong to the same set.
ARR[0][0] belongs to set0. The next element that belongs to set0 will have block number 2048 because 2048 mod 2^{11} = 0.
Block number 2048 will be from row number 2048/512 = 4, because each row has 512 blocks we divide the block number with 512 to get the row number.
From the given options ARR[4][0] will have the same cache index as ARR[0][0].
Block size = 16 Bytes
Number of blocks in the cache = 64KB / 16B = 4K
It is 2way set associative cache, so each set contains 2 blocks.
So, number of sets = 4K / 2 = 2K = 2^{11}
Each element size = 8B and size of each block = 16 B
No. of elements in one block = 16/8 = 2 We know no. of elements in one row of the array = 1024. So, no. of blocks for one row of the array = 1024/2 = 512
We know there are 2^{11} sets, and each set has two blocks.
For any element to share the same cache index as ARR[0][0], it has to belong to the same set.
ARR[0][0] belongs to set0. The next element that belongs to set0 will have block number 2048 because 2048 mod 2^{11} = 0.
Block number 2048 will be from row number 2048/512 = 4, because each row has 512 blocks we divide the block number with 512 to get the row number.
From the given options ARR[4][0] will have the same cache index as ARR[0][0].
Question 73 
0%  
25%  
50%  
75% 
Question 73 Explanation:
Block size = 16B and it is given that double size is 8B, so one element = 8B.
So in one block 2 elements will be stored.
To store 1024×1024 elements no. of blocks needed = 1024×1024/2 = 2^{20}/2 = 2^{19}.
In each block the first element will be a miss and second element will be a hit because on every miss that entire block is brought into the cache. So, there will be 2^{19} hits and 2^{19} misses. Total no. of references = no. of elements in the array = 2^{20}
⇒hit ratio = No. of hits / Total no. of references
=2^{19}/2^{20} = 1/2 = 0.5
=0.5×100=50%
So in one block 2 elements will be stored.
To store 1024×1024 elements no. of blocks needed = 1024×1024/2 = 2^{20}/2 = 2^{19}.
In each block the first element will be a miss and second element will be a hit because on every miss that entire block is brought into the cache. So, there will be 2^{19} hits and 2^{19} misses. Total no. of references = no. of elements in the array = 2^{20}
⇒hit ratio = No. of hits / Total no. of references
=2^{19}/2^{20} = 1/2 = 0.5
=0.5×100=50%
Question 74 
θ(n) and θ(n)  
θ(2^{n}) and θ(n)  
θ(n) and θ(2^{n})
 
θ(2^{n}) and θ(2^{n})

Question 74 Explanation:
Time complexity of f1 is given by
T(n) = T(n1) + T(n2) (multiplication by 2 and 3 won't affect complexity as it is a constant time operation)
T(0) = T(1) = 1
The recurrence is similar to fibonacci series. The time complexity is O(2^{n})
T(n) = T(n1) + T(n2) + c
T(0) = 1
T(n1) ≈ T(n2)
But in reality, T(n1) > T(n2)
So to find upper bound the expression will be
T(n) = 2T(n1) + c
= 4T(n2) + 3c
= 8T(n3) +7c
= 2^{k}T(nk) + (2^{k}1)c
nk=0 ⇒ k = n
T(n) = 2^{n}T(0) + (2^{n}1)c
= 2^{n} +(2^{n}1)c
⇒ T(n) = O(2^{n})
The time required for f2 is O(n) (because it consists of only one loop).
T(n) = T(n1) + T(n2) (multiplication by 2 and 3 won't affect complexity as it is a constant time operation)
T(0) = T(1) = 1
The recurrence is similar to fibonacci series. The time complexity is O(2^{n})
T(n) = T(n1) + T(n2) + c
T(0) = 1
T(n1) ≈ T(n2)
But in reality, T(n1) > T(n2)
So to find upper bound the expression will be
T(n) = 2T(n1) + c
= 4T(n2) + 3c
= 8T(n3) +7c
= 2^{k}T(nk) + (2^{k}1)c
nk=0 ⇒ k = n
T(n) = 2^{n}T(0) + (2^{n}1)c
= 2^{n} +(2^{n}1)c
⇒ T(n) = O(2^{n})
The time required for f2 is O(n) (because it consists of only one loop).
Question 75 
1661 and 1640  
59 and 59  
1640 and 1640
 
1640 and 1661

Question 75 Explanation:
Both functions perform same operation, so output is same, means either (B) or (C) is correct.
f1(2) = 2*f1(1) + 3*f1(0) = 2
f1(3) = 2*f1(2) + 3*f1(1) = 2*2 + 3*1 = 7
f1(4) = 2*f1(3) + 3*f1(2) = 2*7 + 3*2 = 20
f1(5) = 2*f1(4) + 3*f1(3) = 2*20 + 3*7 = 40 + 21 = 61
We can skip after this as the only remaining choice is (C).
f1(6) = 2*f1(5) + 3*f1(4) = 2*61 + 3*20 = 122 + 60 = 182
f1(7) = 2*f1(6) + 3*f1(5) = 2*182 + 3*61 = 364 + 183 = 547
f1(8) = 2*f1(7) + 3*f1(6) = 2*547 + 3*182 = 1094 + 546 = 1640
f1(2) = 2*f1(1) + 3*f1(0) = 2
f1(3) = 2*f1(2) + 3*f1(1) = 2*2 + 3*1 = 7
f1(4) = 2*f1(3) + 3*f1(2) = 2*7 + 3*2 = 20
f1(5) = 2*f1(4) + 3*f1(3) = 2*20 + 3*7 = 40 + 21 = 61
We can skip after this as the only remaining choice is (C).
f1(6) = 2*f1(5) + 3*f1(4) = 2*61 + 3*20 = 122 + 60 = 182
f1(7) = 2*f1(6) + 3*f1(5) = 2*182 + 3*61 = 364 + 183 = 547
f1(8) = 2*f1(7) + 3*f1(6) = 2*547 + 3*182 = 1094 + 546 = 1640
Question 76 
The instruction following the conditional branch instruction in memory is executed.  
The first instruction in the fall through path is executed.
 
The first instruction in the taken path is executed.
 
The branch takes longer to execute than any other instruction. 
Question 76 Explanation:
In order to avoid the pipeline delay due to conditional branch instruction, a suitable instruction is placed below the conditional branch instruction such that the instruction will be executed irrespective of whether branch is taken or not and won't affect the program behaviour. Hence option A is the answer.
Question 77 
I1  
I2  
I3  
I4 
Question 77 Explanation:
It is the method to maximize the use of the pipeline by finding and executing an instruction that can be safely executed whether the branch is taken or not. So, when a branch instruction is encountered, the hardware puts the instruction following the branch into the pipe and begins executing it. Here we do not need to worry about whether the branch is taken or not, as we do not need to clear the pipe because no matter whether the branch is taken or not, we know the instruction is safe to execute.
From the given set of instructions I3 is updating R1, and the branch condition is based on the value of R1 so I3 can’t be executed in the delay slot.
Instruction I1 is updating the value of R2 and R2 is used in I3. So I1 also can’t be executed in the delay slot.
Instruction I2 is updating R4, and at the memory location represented by R4 the value of R1 is stored. So if I2 is executed in the delay slot then the memory location where R1 is to be stored as part of I4 will be in a wrong place. Hence between I2 and I4, I2 can’t be executed after I4. Hence I2 can’t be executed in the delay slot.
Instruction I4 can be executed in the delay slot as this is storing the value of R1 in a memory location and executing this in the delay slot will have no effect. Hence option D is the answer.
From the given set of instructions I3 is updating R1, and the branch condition is based on the value of R1 so I3 can’t be executed in the delay slot.
Instruction I1 is updating the value of R2 and R2 is used in I3. So I1 also can’t be executed in the delay slot.
Instruction I2 is updating R4, and at the memory location represented by R4 the value of R1 is stored. So if I2 is executed in the delay slot then the memory location where R1 is to be stored as part of I4 will be in a wrong place. Hence between I2 and I4, I2 can’t be executed after I4. Hence I2 can’t be executed in the delay slot.
Instruction I4 can be executed in the delay slot as this is storing the value of R1 in a memory location and executing this in the delay slot will have no effect. Hence option D is the answer.
Question 78 
x_{n} = 2x_{n1}
 
x_{n} = x_{⌊n/2⌋}+1
 
x_{n} = x_{⌊n/2⌋}+n
 
x_{n} = x_{n1}+x_{n2}

Question 78 Explanation:
x_{n} = number of binary strings of length contains nonconsecutive 0’s.
Let us consider n=1
Possible binary strings: 0, 1
x_{1} = 2
⇒ n = 2; binary strings not containing consecutive zero’s
11,01,10
x_{2} = 3
⇒ For n=3, then possible strings are
⇒ For n=4; then possible strings are
Let us consider n=1
Possible binary strings: 0, 1
x_{1} = 2
⇒ n = 2; binary strings not containing consecutive zero’s
11,01,10
x_{2} = 3
⇒ For n=3, then possible strings are
⇒ For n=4; then possible strings are
Question 79 
5  
7  
8  
16 
Question 79 Explanation:
Asked for no. of binary strings of length 5 contains nonconsecutive zeros.
Case 1: When string contains no zero,
1 1 1 1 1
No. of ways = 1
Case 2: When string contains only one zero
× 1 × 1 × 1 × 1 ×
It can be placed any of the five places above shown with cross mark.
So no. of ways = ^{5}C_{1} = 5
Case 3: When string contains only two zero's.
× 1 × 1 × 1 ×
The two zero's can be placed any of the four places above shown with cross marks,
So no. of ways = ^{4}C_{2} = 6
Case 4: When string contains only three zero's.
× 1 × 1 ×
The three zero's can be placed at any of the three places above shown with cross marks.
So no. of ways = ^{3}C_{3} = 1
Four zero's and five zero's cannot be placed in the string because whatever you try to put it in the length of string 5, the two consecutive zero will come. So therefore total no. of ways possible.
= 1+5+6+1
= 13
None of the given option is correct.
Case 1: When string contains no zero,
1 1 1 1 1
No. of ways = 1
Case 2: When string contains only one zero
× 1 × 1 × 1 × 1 ×
It can be placed any of the five places above shown with cross mark.
So no. of ways = ^{5}C_{1} = 5
Case 3: When string contains only two zero's.
× 1 × 1 × 1 ×
The two zero's can be placed any of the four places above shown with cross marks,
So no. of ways = ^{4}C_{2} = 6
Case 4: When string contains only three zero's.
× 1 × 1 ×
The three zero's can be placed at any of the three places above shown with cross marks.
So no. of ways = ^{3}C_{3} = 1
Four zero's and five zero's cannot be placed in the string because whatever you try to put it in the length of string 5, the two consecutive zero will come. So therefore total no. of ways possible.
= 1+5+6+1
= 13
None of the given option is correct.
Question 80 
X[i, j] = X[i  1, j] ∨ X[i, j  a^{i}]
 
X[i, j] = X[i  1, j] ∨ X[i  1, j  a^{i}]
 
X[i, j] = X[i  1, j] ∧ X[i, j  a^{i}]
 
X[i, j] = X[i  1, j] ∧ X[i 1, j  a^{i}] 
Question 80 Explanation:
X[I, j] (2 <= i <= n and a^{i} <= j <= W) is true if any of the following is true.
1) Sum of weights excluding a^{i} is equal to j, i.e., if X[i1, j] is true.
2) Sum of weights including a^{i} is equal to j, i.e., if X[i1, ja^{i}] is true so that we get (j – a^{i}) + a^{i} as j.
1) Sum of weights excluding a^{i} is equal to j, i.e., if X[i1, j] is true.
2) Sum of weights including a^{i} is equal to j, i.e., if X[i1, ja^{i}] is true so that we get (j – a^{i}) + a^{i} as j.
Question 81 
X[1, W]
 
X[n, 0]  
X[n, W]  
X[n1, n] 
Question 81 Explanation:
The last row and last column given the value is 1 then subset of whose elements sum to W.
Note: As per present GATE syllabus, this concept is not required.
Note: As per present GATE syllabus, this concept is not required.
Question 82 
2  
3  
4  
5 
Question 82 Explanation:
➝ M, P are entities so they require individual tables.
➝ Here N is a Weak entity, but it need to modify the primary key of P such as P1
M = {M1, M2, M3, P1}
P = {P1, P2}
N = {N1, N2, P1}
➝ Relationship set has its own attribute, then no need to create a separate table.
➝ Finally we require 3 minimum tables to represent M,P,N,R1,R2.
➝ Here N is a Weak entity, but it need to modify the primary key of P such as P1
M = {M1, M2, M3, P1}
P = {P1, P2}
N = {N1, N2, P1}
➝ Relationship set has its own attribute, then no need to create a separate table.
➝ Finally we require 3 minimum tables to represent M,P,N,R1,R2.
Question 83 
{M1, M2, M3, P1}  
{M1, P1, N1, N2}
 
{M1, P1, N1}  
{M1, P1}

Question 83 Explanation:
Possible set of attributes is
For M = {M1, M2, M3, P1}
P = {P1, P2}
N = {N1, N2, P1}
For M = {M1, M2, M3, P1}
P = {P1, P2}
N = {N1, N2, P1}
Question 84 
Y is [1 2 3 4 5 6 7 8 9 10] and x < 10
 
Y is [1 3 5 7 9 11 13 15 17 19] and x < 1
 
Y is [2 2 2 2 2 2 2 2 2 2] and x > 2
 
Y is [2 4 6 8 10 12 14 16 18 20] and 2 < x < 20 and x is even

Question 84 Explanation:
This program doesn’t work for the cases where element to be searched is the last element of Y[ ] or greater than the last element (or maximum element) in Y[ ]. In such case, program goes in an infinite loop because i is assigned value as k in all iterations, and i never becomes same/ equal to or greater than j. So while condition never becomes false.
Question 85 
Change line 6 to: if (Y[k] < x) i = k + 1; else j = k1;
 
Change line 6 to: if (Y[k] < x) i = k  1; else j = k+1;
 
Change line 6 to: if (Y[k] <= x) i = k; else j = k;
 
Change line 7 to: } while ((Y[k] == x) && (i < j));

Question 85 Explanation:
f(int Y[10], int x)
{
int i,j,k;
i=0;j=9;
do
{
k=(i+j)/2;
if(Y[k]
i=k+1;
else
j=k1;
} while (Y[k]!=x && i
if (Y[k]= =x)
printf(“x is in the array”);
else
printf(“x is not in the array”);
}
{
int i,j,k;
i=0;j=9;
do
{
k=(i+j)/2;
if(Y[k]
else
j=k1;
} while (Y[k]!=x && i
printf(“x is in the array”);
else
printf(“x is not in the array”);
}
There are 85 questions to complete.