GATE 2014 [Set1]
Question 1 
Which of the following options is the closest in meaning to the phrase underlined in the sentence below? It is fascinating to see life forms cope with varied environmental conditions.
adopt to  
adapt to  
adept in  
accept with 
(1) Adopt ⇒ Legally take and bring it up as one's own.
(2) Adapt ⇒ Make suitable for a new use or purpose.
(3) Adept ⇒ Very skilled (or) proficienct at something.
(4) Accept ⇒ Believe (or) come to recognize as valid (or) correct.
Option B is correct.
Question 2 
Choose the most appropriate word from the options given below to complete the following sentence. He could not understand the judges awarding her the first prize, because he thought that her performance was quite __________.
superb  
medium  
mediocre  
exhilarating 
Question 3 
In a press meet on the recent scam, the minister said, "The buck stops here". What did the minister convey by the statement?
He wants all the money  
He will return the money  
He will assume final responsibility  
He will resist all enquiries 
⇒ It represents that this is the final stage of responsibility.
Question 4 
If (z + 1/z)^{2 } = 98, compute (z^{2}+ 1/z^{2}).
96  
97  
98  
99 
= 98
⇒ z^{2} + 1/z^{2}
= 96
Question 5 
The roots of ax^{2} + bx + c = 0 are real and positive. a, b and c are real. Then ax^{2} + bx+ c = 0 has
no roots  
2 real roots  
3 real roots  
4 real roots 
For roots to be real & positive b^{2}4ac>0
This will have 2 real positive roots.
ax^{2}+bx+c = 0
Discriminant = b^{2}4ac>0
ax^{2}+bx+c
(b)^{2}4ac
⇒ b^{2}4ac
Is also > 0. This will have real roots.
⇒ This will have 4 real roots.
Question 6 
The Palghat Gap (or Palakkad Gap), a region about 30 km wide in the southern part of the Western Ghats in India, is lower than the hilly terrain to its north and south. The exact reasons for the formation of this gap are not clear. It results in the neighbouring regions of Tamil Nadu getting more rainfall from the South West monsoon and the neighbouring regions of Kerala having higher summer temperatures. What can be inferred from this passage?
The Palghat gap is caused by high rainfall and high temperatures in southern Tamil Nadu and Kerala  
The regions in Tamil Nadu and Kerala that are near the Palghat Gap are lowlying  
The low terrain of the Palghat Gap has a significant impact on weather patterns in neighbouring parts of Tamil Nadu and Kerala  
Higher summer temperatures result in higher rainfall near the Palghat Gap area 
⇒ Option C is suitable option.
Question 7 
Geneticists say that they are very close to confirming the genetic roots of psychiatric illnesses such as depression and schizophrenia, and consequently, that doctors will be able to eradicate these diseases through early identification and gene therapy. On which of the following assumptions does the statement above rely?
Strategies are now available for eliminating psychiatric illnesses  
Certain psychiatric illnesses have a genetic basis  
All human diseases can be traced back to genes and how they are expressed  
In the future, genetics will become the only relevant field for identifying psychiatric illnesses 
⇒ Option B is the only option that contain illness.
Question 8 
Roundtrip tickets to a tourist destination are eligible for a discount of 10% on the total fare. In addition, groups of 4 or more get a discount of 5% on the total fare. If the one way single person fare is Rs 100, a group of 5 tourists purchasing roundtrip tickets will be charged Rs _________.
850  
851  
852  
853 
Round trip, there is a discount of 10% of total fare.
Group of 4 or more, Discount of 5% of total fare.
∴ 5 tourists ⇒ Total fare = 5 × 200 = 1000
Total discount = 10% of 1000 + 5% of 1000
= 100 + 50
= ₹150
∴ Fare charged = 1000  150 = ₹850
Question 9 
In a survey, 300 respondents were asked whether they own a vehicle or not. If yes, they were further asked to mention whether they own a car or scooter or both. The irresponses are tabulated below. What percent of respondents do not own a scooter?
48  
49  
50  
51 
[No. of respondents who do not own a scooter] = [No. of respondents who own's only a car + No. of respondents who do not own any vehicle]
= 40 + 34 + 70
= 144
Percentage = 144/300 × 100 = 48%
Question 10 
When a point inside of a tetrahedron (a solid with four triangular surfaces) is connected by straight lines to its corners, how many (new) internal planes are created with these lines? __________.
6  
7  
8  
9 
→ If you take a point inside a tetrahedron, then you have 5 points.
→ An internal plane is formed by joining any of the three points.
→ No. of planes = ^{5} C _{3} = 10
But 4 of them will be faces of tetrahedron.
∴ New planes = 10  4 = 6
Question 11 
Consider the statement
“Not all that glitters is gold”
Predicate glitters(x) is true if x glitters and predicate gold(x) is true if x is gold. Which one of the following logical formulae represents the above statement?
∀x: glitters(x) ⇒ ¬gold(x)  
∀x: gold(x) ⇒ glitters()  
∃x: gold(x) ∧ ¬glitters(x)  
∃x: glitters(x) ∧ ¬gold(x) 
Not all that glitters is gold.
Option A:
∀x:glitters(x) ⇒ ¬gold(x)
which means that every item (x), which glitters is not gold.
Option B:
∀x:gold(x) ⇒ glitters()
Every item (x) which is gold is a glitter.
(or)
Every golden item glitters.
Option C:
∃x: gold(x) ∧ ¬glitters(x)
There are some gold items which does not glitters.
Option D:
∃x:glitters(x) ∧ ¬gold(x)
There exists some glitters which are not gold.
(or)
Not all glitters are gold.
The answer is Option (D).
Method 2:
⇒ (∼∀x) (∼ (glitters(x) ⇒ gold(x))
⇒ ∃x (∼ (∼glitters(x) ∨ gold(x))
⇒ ∃x (glitters ∧ gold(x))
Question 12 
Suppose you break a stick of unit length at a point chosen uniformly at random. Then the expected length of the shorter stick is ________.
0.25  
0.26  
0.27  
0.28 
If we break at point x, length of the one piece x and the other piece is 1 – x.
Length of the shorter stick is between 0 to 0.5. If it is more than 0.5 then it will be longer stick.
The random variable (l) follows a uniform distribution. The probability function of l is
1/(ba)=1/(0.50)=2 (length is between 0 to 0.5)
Expected value of length
(where P(l) is the probability density function)
Question 13 
Let G = (V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G?
G_{1}=(V,E_{1}) where E_{1}={(u,v)(u,v)∉E}  
G_{2}=(V,E_{2} )where E_{2}={(u,v)│(u,v)∈E}  
G_{3}=(V,E_{3}) where E_{3}={(u,v)there is a path of length≤2 from u to v in E}  
G_{4}=(V_{4},E) where V_{4} is the set of vertices in G which are not isolated 
→ It strongly connected.
(A) G_{1}=(V,E_{1}) where E_{1}={(u,v)(u,v)∉E}
If (u, v) does not belong to the edge set ‘E’, then it indicates there are no edges. So, it is not connected.
(B) G_{2}=(V,E_{2} )where E_{2}={(u,v)│(u,v)∈E}
Given that ‘G’ is directed graph, i.e., it has path from each vertex to every other vertex.
Though direction is changed from (u, v) to (v, u), it is still connected component same as ‘G’.
(C) G_{3}=(V,E_{3}) where E_{3}={(u,v)there is a path of length≤2 from u to v in E}
This can also be true.
eg:
Both from each vertex to other vertex is also exists. So it is also strongly connected graph.
(D) G_{4}=(V_{4},E) where V_{4} is the set of vertices in G which are not isolated.
If ‘G’ has same ‘x’ no. of isolated vertices, one strongly connected component
then no. of SCC = x + 1
G_{4} contain only ‘1’ component, which is not same as G.
Question 14 
Consider the following system of equations:
 3x + 2y = 1
4x + 7z = 1
x + y + z = 3
x – 2y + 7z = 0
The number of solutions for this system is _______.
1  
2  
3  
4 
3x + 2y = 1
4x + 7z = 1
x + y + z = 3
x – 2y + 7z = 0
This is a nonhomogeneous equation system.
The Augmented matrix for above set of equations is
For matrix (A):
R_{4}→ R_{4}+R_{1}
R_{4}→ R_{4}R_{2}
Rank = 3
For matrix (AB):
R_{4}→(R_{4}+R_{1} )R_{2}
Rank = 3
Rank of (A) = Rank (AB), so Unique solution
rank = 3 = no. of variables
Working Rule for Nonhomogeneous equation:
(1) rank (A) < rank (AB), Inconsistent solution
(2) is rank (A) = rank (AB) = r then
if r = n, Unique solution
r < n, Infinite solution
Question 15 
The value of the dot product of the eigenvectors corresponding to any pair of different eigenvalues of a 4by4 symmetric positive definite matrix is ________.
0  
1  
2  
3 
The finite dimensional spectral theorem says that any symmetric matrix whose entries are real can be diagonalized by an orthogonal matrix.
Question 16 
Let the function
where and f(θ) denote the derivative of f with respect to θ. Which of the following is/are TRUE?

(I) There exists such that such that f(θ)=0.
(II) There exists such that such that f(θ)≠0.
I only  
II only  
Both I and II  
Neither I nor II 
Rolle’s theorem states that for any continuous, differentiable function that has two equal values at two distinct points, the function must have a point on the function where the first derivative is zero. The technical way to state this is: if f is continuous and differentiable on a closed interval [a,b] and if f(a) = f(b), then f has a minimum of one value c in the open interval [a, b] so that f'(c) = 0.
We can observe that, sin, cos are continuous, but, Tan is not continuous at π/2. As the mentioned interval does not contain π/2, we can conclude that it is continuous.
As per Rolls theorem both statement 1 and statement 2 are true.
Question 17 
Consider the following Boolean expression for F:
F(P, Q, R, S) = PQ + P'QR + P'QR'S
The minimal sumofproducts form of F is
= Q(P+P’R) + P’QR’S
= Q(P+R) + P’QR’S
= QP + QR + P’QR’S
= QP + Q(R + P’R’S)
= QP + Q( R + P’S)
= QP + QR + QP’S
= Q(P+P’S) + QR
= Q(P+S)+ QR
= QP + QS + QR
Question 18 
The base (or radix) of the number system such that the following equation holds is_________.
312/20 = 13.1
5  
6  
7  
8 
(3r^{2} + r + 2) / 2r= (r+3+1/r)
(3r^{2} + r + 2) / 2r= (r^{2}+3r+1) / r
(3r^{2} + r + 2) = (2r^{2}+6r+2)
r^{2} 5r = 0
Therefor r = 5
Question 19 
A machine has a 32bit architecture, with 1word long instructions. It has 64 registers, each of which is 32 bits long. It needs to support 45 instructions, which have an immediate operand in addition to two register operands. Assuming that the immediate operand is an unsigned integer, the maximum value of the immediate operand is ________.
16383  
16384  
16385  
16386 
Each instruction has 32 bits.
To support 45 instructions, opcode must contain 6bits.
Register operand1 requires 6 bits, since the total registers are 64.
Register operand 2 also requires 6 bits
14bits are left over for immediate Operand using 14bits, we can give maximum 16383, Since 2^{14} = 16384 (from 0 to 16383)
Question 20 
Consider the following program in C language:
#includemain() { int i; int *pi = &i; scanf("%d", pi); printf("%dn", i+5); }
Which one of the following statements is TRUE?
Compilation fails.  
Execution results in a runtime error.  
On execution, the value printed is 5 more than the address of variable i.  
On execution, the value printed is 5 more than the integer value entered. 
int *pi = &i; // pi is a pointer which stores the address of i.
scanf (pi); // pi = &i (we rewrite the garbage value with our values) say x = 2
printf (i+5); // i+5 = x+5 = 2+5 = 7
Hence on execution, the value printed is 5 more than the integer value entered.
Question 21 
Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?
θ(n)  
θ(n+m)  
θ(n^{2})  
θ(m^{2}) 
Question 22 
Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly 4 nodes is O(n^{a}log^{b}n). Then the value of a+10b is ________.
1  
2  
3  
4 
Substitute into a and b values in equation.
⇒ a+10b
⇒ a*1 + 10*0
⇒ 1+0
⇒ 1
Question 23 
Consider the directed graph given below.
Which one of the following is TRUE?
The graph does not have any topological ordering.  
Both PQRS and SRQP are topological.  
Both PSRQ and SPRQ are topological orderings.  
PSRQ is the only topological ordering. 
There are no cycles in the graph, so topological orderings do exist.
We can consider P & S as starting vertex, followed by R & Q.
Hence, PSRQ & SPRQ are the topological orderings.
Question 24 
Let P be a quicksort program to sort numbers in ascending order using the first elements as the pivot. Let t_{1} and t_{2} be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?
t_{1}=5  
t_{1}  
t_{1}>t_{2}  
t_{1}=t_{2} 
Simple one: First element is a pivot element. And if we observe first array pivot is small and requires lot of comparisons and whereas it is not the case with 2^{nd} array through not in sorted manner.
Hence t_{1}> t_{2}.
Question 25 
Which one of the following is TRUE?
The language L={a^{n} b^{n}│n≥0} is regular.  
The language L={a^{n}│n is prime} is regular.  
The language L={w│w has 3k+1b's for some k∈N with Σ={a,b} } is regular.  
The language L={ww│w∈Σ* with Σ={0,1} } is regular. 
L = {a^{n}  n is prime} is CSL, as calculation of “n is prime” can be done by LBA (Turing machine)
L = {ww  w ∈ ∑*} is CSL.
But L = { w  w has 3k+1 b’s for some k ∈ natural number} is regular.
Lets take values of k={1,2,3,….}
So number of b’s will be {4, 7, 10,……….} and number of a’s can be anything.
The DFA will be
Question 26 
Consider the finite automaton in the following figure.
What is the set of reachable states for the input string 0011?
{q_{0}, q_{1}, q_{2}}  
{q_{0}, q_{1}}  
{q_{0}, q_{1}, q_{2}, q_{3}}  
{q_{3}} 
{q_{0} , 0 → q_{0}} , { q_{0} , 0 → q_{0} }, {q_{0} , 1 → q_{0}}, {q_{0} , 1 → q_{1}} . Hence δ (q_{0}, 0011) = q_{1}
{q_{0} , 0 → q_{0}} , { q_{0} , 0 → q_{0} }, {q_{0} , 1 → q_{1}}, {q_{1} , 1 → q_{2}} . Hence δ (q_{0}, 0011) = q_{2}
Hence δ (q_{0}, 0011) = {q_{0}, q_{1}, q_{2}}
Question 27 
Which one of the following is FALSE?
A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end.  
Available expression analysis can be used for common subexpression elimination.  
Live variable analysis can be used for dead code elimination.  
x=4*5 ⇒ x=20 is an example of common subexpression elimination. 
Common subexpression elimination (CSE) is a compiler optimization that searches for instances of identical expressions (i.e., they all evaluate to the same value), and analyzes whether it is worthwhile replacing them with a single variable holding the computed value.
For ex: Consider the following code:
m=y+z * p
n= y+z *k
The common subexpression is “y+z” we can be calculate it one time and replace in both expression
temp = y+z
m = temp*p
n = temp*k
Question 28 
Match the following:
1) Waterfall model a) Specifications can be developed incrementally 2) Evolutionary model b) Requirements compromises are inevitable 3) Componentbased c) Explicit recognition of risk software engineering 4) Spiral development d) Inflexible partitioning of the project into stages
1a, 2b, 3c, 4d  
1d, 2a, 3b, 4c  
1d, 2b, 3a, 4c  
1c, 2a, 3b, 4d 
Question 29 
Suppose a disk has 201 cylinders, numbered from 0 to 200. At some time the disk arm is at cylinder 100, and there is a queue of disk access requests for cylinders 30, 85, 90, 100, 105, 110, 135 and 145. If ShortestSeek Time First (SSTF) is being used for scheduling the disk access, the request for cylinder 90 is serviced after servicing ____________ number of requests.
3  
4  
5  
6 
90 is serviced after servicing three requests, i.e.,
100 → 105 → 110 → 90
Question 30 
Which one of the following is FALSE?
User level threads are not scheduled by the kernel.  
When a user level thread is blocked, all other threads of its process are blocked.  
Context switching between user level threads is faster than context switching between kernel level threads.  
Kernel level threads cannot share the code segment. 
Question 31 
Consider the relation scheme R = (E, F, G, H, I, J, K, L, M, N) and the set of functional dependencies {{E,F} → {G}, {F} → {I,J}, {E,H} → {K,L}, {K} → {M}, {L} → {N}} on R. What is the key for R?
{E,F}  
{E,F,H}  
{E,F,H,K,L}  
{E} 
B) (EFH)^{+} = EFHGIJKLMN, EFH is deriving all the attributes of R. So, EFH is a key.
C) If EFH is a key, then EFHKL will become the super key.
D) (E)^{+} = E
Question 32 
Given the following statements:
S1: A foreign key declaration can always be replaced by an equivalent check assertion in SQL. S2: Given the table R(a,b,c) where a and b together form the primary key, the following is a valid table definition. CREATE TABLE S ( a INTEGER, d INTEGER, e INTEGER, PRIMARY KEY (d), FOREIGN KEY (a) references R)
Which one of the following statements is CORRECT?
S1 is TRUE and S2 is FALSE.  
Both S1 and S2 are TRUE.  
S1 is FALSE and S2 is TRUE.  
Both S1 and S2 are FALSE. 
Using a check constraint, we can have the same effect as foreign key while adding elements to the child table. But while deleting elements from the parent table the referential integrity constraint is no longer valid. So, a check constraint cannot replace a foreign key.
S2: False:
Foreign key in one table should be defined as a primary key in other table. In above table definition, table S has a foreign key that refers to field ‘a’ of R. The field ‘a’ in table S is part of the primary key and part of the key cannot be declared as a foreign key.
Question 33 
Consider the following three statements about link state and distance vector routing protocols, for a large network with 500 network nodes and 4000 links.

[S1] The computational overhead in link state protocols is higher than in distance vector protocols.
[S2] A distance vector protocol (with split horizon) avoids persistent routing loops, but not a link state protocol.
[S3] After a topology change, a link state protocol will converge faster than a distance vector protocol.
Which one of the following is correct about S1, S2, and S3 ?
S1, S2, and S3 are all true.  
S1, S2, and S3 are all false.  
S1 and S2 are true, but S3 is false.  
S1 and S3 are true, but S2 is false. 
S2: A distance vector protocol with split horizon avoid persistent routing loops is true, but not a link state protocol is false because link state protocols do not have count to infinity problem.
S3: As Distance vector protocol has count to infinity problem and converges slower. (True)
Question 34 
Which of the following are used to generate a message digest by the network security protocols?
 (P) RSA
(Q) SHA1
(R) DES
(S) MD5
P and R only  
Q and R only  
Q and S only  
R and S only 
Question 35 
Identify the correct order in which the following actions take place in an interaction between a web browser and a web server.

2. The web browser establishes a TCP connection with the web server.
3. The web server sends the requested webpage using HTTP.
4. The web browser resolves the domain name using DNS.
4,2,1,3  
1,2,3,4  
4,1,2,3  
2,4,1,3 
Question 36 
Consider a token ring network with a length of 2 km having 10 stations including a monitoring station. The propagation speed of the signal is 2×10^{8} m/s and the token transmission time is ignored. If each station is allowed to hold the token for 2 µsec, the minimum time for which the monitoring station should wait (in µsec) before assuming that the token is lost is _______.
28μs to 30 μs  
29μs to 31 μs  
30μs to 32 μs  
31μs to 33 μs 
No. of Stations (m) = 10
Propagation speed (v) = 2⨯10^{8} m/s
THT = 2μs
So, Max, TRT = T_{p} in the ring + No. of Active Stations * THT
= 10 ⨯ 10^{6} + 10 ⨯ 2 ⨯ 10^{6}
= 30 μs
Question 37 
Let the size of congestion window of a TCP connection be 32 KB when a timeout occurs. The round trip time of the connection is 100 msec and the maximum segment size used is 2 KB. The time taken (in msec) by the TCP connection to get back to 32 KB congestion window is _________.
1100 to 1300  
1101 to 1301  
1102 to 1302  
1103 to 1303 
When Time Out occurs, for the next round of Slow Start, Threshold = (size of Cwnd) / 2
It means Threshold = 16KB
Slow Start
2KB
1RTT
4KB
2RTT
8KB
3RTT
16KB  Threshold reaches. So Additive Increase Starts
4RTT
18KB
5RTT
20KB
6RTT
22KB
7RTT
24KB
8RTT
26KB
9RTT
28KB
10RTT
30KB
11RTT
32KB
So, Total no. of RTTs = 11 → 11 * 100 = 1100
Question 38 
Consider a selective repeat sliding window protocol that uses a frame size of 1 KB to send data on a 1.5 Mbps link with a oneway latency of 50 msec. To achieve a link utilization of 60%, the minimum number of bits required to represent the sequence number field is ________.
5  
6  
7  
8 
B = 1.5 Mbps
T_{p} = 50 ms
η = 60%
Efficiency formula for SR protocol is
η = W/(1+2a) ⇒ 60/100 = W/(1+2a) (∵a = T_{p}/T_{x})
T_{x} = L/B = 8×10^{3}/1.5×10^{6} = 5.3ms
a = T_{p}/T_{x} = 50/5.3 = 500/53 = 9.43
⇒ 60/100 = W/19.86 ⇒ W = 11.9 ≈ 12
⇒ W = 2^{n1} = 12 ⇒ 2^{n} = 24 ⇒ 2^{n} = 24 ≈ 2^{5} ⇒ n = 5
Question 39 
Consider the following four schedules due to three transactions (indicated by the subscript) using read and write on a data item x, denoted by r(x) and w(x) respectively. Which one of them is conflict serializable?
r_{1} (x); r_{2} (x); w_{1} (x); r_{3} (x); w_{2} (x)  
r_{2} (x);r_{1} (x);w_{2} (x);r_{3} (x);w_{1} (x)  
r_{3} (x);r_{2} (x);r_{1} (x);w_{2} (x);w_{1} (x)  
r_{2} (x);w_{2} (x);r_{3} (x);r_{1} (x);w_{1} (x) 
 Polygraph contains cycle. So, not a conflict serializable.
Option: B
Cyclic
Option: C
 Cyclic
Option: D
 Acyclic, so conflict serializable.
Question 40 
Given the following two statements:
S1: Every table with two singlevalued attributes is in 1NF, 2NF, 3NF and BCNF. S2: AB>C, D>E, E>C is a minimal cover for the set of functional dependencies AB>C, D>E, AB>E, E>C.
Which one of the following is CORRECT?
S1 is TRUE and S2 is FALSE.  
Both S1 and S2 are TRUE.  
S1 is FALSE and S2 is TRUE.  
Both S1 and S2 are FALSE. 
If we can prove the relation is in BCNF then by default it would be in 1NF, 2NF, 3NF also.
Let R(AB) be a two attribute relation, then
If {A→B} exists then BCNF since {A}^{+} = AB = R
If {B→A} exists then BCNF since {B}^{+} = AB = R
If {A→B, B→A} exists then BCNF since A and B both are Super Key now.
If {No nontrivial Functional Dependency} then default BCNF.
Hence it’s proved that a Relation with two singlevalued attributes is in BCNF hence it’s also in 1NF, 2NF, 3NF.
S2: False
The canonical cover for the given FD set is {AB→C, D→E, AB→E, E→C}. As we can see AB→E is not covered in minimal cover since {AB}^{+} = ABC in the given cover {AB→C, D→E, E→C}
Question 41 
An operating system uses the Banker’s algorithm for deadlock avoidance when managing the allocation of three resource types X, Y, and Z to three processes P0, P1, and P2. The table given below presents the current system state. Here, the Allocation matrix shows the current number of resources of each type allocated to each process and the Max matrix shows the maximum number of resources of each type required by each process during its execution.
There are 3 units of type X, 2 units of type Y and 2 units of type Z still available. The system is currently in a safe state. Consider the following independent requests for additional resources in the current state:
REQ1: P0 requests 0 units of X, 0 units of Y and 2 units of Z REQ2: P1 requests 2 units of X, 0 units of Y and 0 units of Z
Which one of the following is TRUE?
Only REQ1 can be permitted.  
Only REQ2 can be permitted.  
Both REQ1 and REQ2 can be permitted.  
Neither REQ1 nor REQ2 can be permitted. 
After allowing Req 1,
Available: X=3, Y=2, Z=0
With this we can satisfy P1's requirement. So available becomes: X=6, Y=4, Z=0.
Since Z is not available, neither P0's nor P2's requirement can be satisfied. So, it is an unsafe state.
Lets take 2nd case,
After allowing Req 2,
Available: X=1, Y=2, Z=2
With this we can satisfy any one of P1's or P2's requirement. Lets first satisfy P1's requirement. So Available now becomes:
X=6, Y=4, Z=2
Now with the availability we can satisfy P2's requirement. So Available now becomes,
X=8, Y=5, Z=3
With this availability P0 can also be satisfied. So, hence it is in safe state.
So from above two cases Req 1 cannot be permitted but Req 2 can be permitted.
Question 42 
Consider the following set of processes that need to be scheduled on a single CPU. All the times are given in milliseconds.
Using the shortest remaining time first scheduling algorithm, the average process turnaround time (in msec) is ________.
7.2  
7.3  
7.4  
7.5 
TAT(A) = 80 = 8, TAT(B)= 53=2, TAT(C)= 125=7, TAT(D)= 217= 14, TAT(E)=1510=5
Average turnaround time = 8+2+7+14+5/ 5 = 7.2ms
Question 43 
Assume that there are 3 page frames which are initially empty. If the page reference string is 1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6, the number of page faults using the optimal replacement policy is__________.
7  
8  
9  
10 
Total 7 faults are there.
Question 44 
A canonical set of items is given below
S > L. > R Q > R.
On input symbol < the set has
a shiftreduce conflict and a reducereduce conflict.  
a shiftreduce conflict but not a reducereduce conflict.  
a reducereduce conflict but not a shiftreduce conflict.  
neither a shiftreduce nor a reducereduce conflict. 
But if it would have asked about “>” then it will be a SR conflict.
Question 45 
Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility?
Neither L nor is recursively enumerable (r.e.).  
One of L and is r.e. but not recursive; the other is not r.e.  
Both L and are r.e. but not recursive.  
Both L and are recursive. 
Question 46 
Which of the regular expressions given below represent the following DFA?

I) 0*1(1+00*1)*
II) 0*1*1+11*0*1
III) (0+1)*1
I and II only  
I and III only  
II and III only  
I, II, and III 
So the regular expression corresponding to DFA is (0+1)*1.
Now, by using state elimination method,
So the DFA also has another equivalent regular expression: 0*1(1+00*1)*.
But the regular expression (0*1*1+11*0*1) is not equivalent to DFA, as the DFA also accept the string “11011” which cannot be generated by this regular expression.
Question 47 
There are 5 bags labeled 1 to 5. All the coins in a given bag have the same weight. Some bags have coins of weight 10 gm, others have coins of weight 11 gm. I pick 1, 2, 4, 8, 16 coins respectively from bags 1 to 5. Their total weight comes out to 323 gm. Then the product of the labels of the bags having 11 gm coins is _______.
12  
13  
14  
15 
No. of coins picked: 1 2 4 8 16
There are two types of weights of coin, i.e., 10gm and 11gm. And total weight of picked coins are 323gm.
Let there be x number of 10gm coins and y number of 11gm coins.
So, 10x + 11y = 323  (1)
And we also know that total number of coins picked is
1 + 2 + 4 + 8 + 16 = 31 which is equal to x + y, so,
= 31  (2)
Solving equation (1) and (2), we get
y = 13
Means total there are 13 coins of 11gm.
Now we can chose bag number 1, 3 and 4, we will get a total sum of 13 coins picked from them.
So product of labelled bag number = 1×3×4 = 12
Question 48 
Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)?
Question 49 
The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is __________.
148  
149  
150  
151 
(∵ T(n) = T(floor(n/2))+T(ceil(n/2))+2)
Question 50 
Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are
3, 0, and 1  
3, 3, and 3  
4, 0, and 1  
3, 0, and 2 
h(k) = k mod 9
Collisions are resolved using chaining.
Keys: 5, 28, 19, 15, 20, 33, 12, 17, 10.
5%9 – 5
28%9 – 1
19%9 – 1
15%9 – 6
20%9 – 2
33%9 – 6
12%9 – 3
17%9 – 8
10%9 – 1
Maximum chain length is 3
Minimum chain length is 0
Average chain length = 0+3+1+1+0+1+2+0+1/ 9 = 1
Question 51 
Consider the following C function in which size is the number of elements in the array E: The value returned by the function MyX is the
int MyX(int *E, unsigned int size) { int Y = 0; int Z; int i, j, k; for(i = 0; i < size; i++) Y = Y + E[i]; for(i = 0; i < size; i++) for(j = i; j < size; j++) { Z = 0; for(k = i; k <= j; k++) Z = Z + E[k]; if (Z > Y) Y = Z; } return Y; }
maximum possible sum of elements in any subarray of array E.  
maximum element in any subarray of array E.  
sum of the maximum elements in all possible subarrays of array E.  
the sum of all the elements in the array E. 
for (i=0; i
for (i=0; i
Z=0;
for(k=i; k<=j; k++)
Z=Z+E[k];
// It calculates the sum of all possible subarrays starting from 0 i.e., the loop will iterate for all the elements of array E and for every element, calculate sum of all sub arrays starting with E[i].
Store the current sum in Z.
If Z is greater than Y then update Y and return Y. So it returns the maximum possible sum of elements in any sub array of given array E.
Question 52 
Consider the following pseudo code. What is the total number of multiplications to be performed?
D = 2 for i = 1 to n do for j = i to n do for k = j + 1 to n do D = D * 3
Half of the product of the 3 consecutive integers.  
Onethird of the product of the 3 consecutive integers.  
Onesixth of the product of the 3 consecutive integers.  
None of the above. 
for i = 1 to n do
for j = i to n do
for k = j + 1 to n do
D = D * 3;
Also you can try for smaller ‘n’.
Question 53 
Consider a 6stage instruction pipeline, where all stages are perfectly balanced. Assume that there is no cycletime overhead of pipelining. When an application is executing on this 6stage pipeline, the speedup achieved with respect to nonpipelined execution if 25% of the instructions incur 2 pipeline stall cycles is _________.
4  
5  
6  
7 
There were 2 stall cycles for pipelining for 25% of the instructions.
So pipeline time =(1+(25/100)*2)=3/2=1.5
Speed up =Nonpipeline time / Pipeline time=6/1.5=4
Question 54 
An access sequence of cache block addresses is of length N and contains n unique block addresses. The number of unique block addresses between two consecutive accesses to the same block address is bounded above by k. What is the miss ratio if the access sequence is passed through a cache of associativity A≥k exercising leastrecentlyused replacement policy?
n/N  
1/N  
1/A  
k/n 
As the set associativity size keeps increasing then we don't have to replace any block, so LRU is not of any significance here.
Question 55 
Consider a 4to1 multiplexer with two select lines S1 and S0, given below
The minimal sumofproducts form of the Boolean expression for the output F of the multiplexer is
= P’Q + PQ’R + PQR’
= Q(P’ + P R’) + PQ’R
= Q(P’ + R’) + PQ’R
= P’Q + QR’ + PQ’R
Question 56 
The function f(x) = x sinx satisfies the following equation: f''(x) + f(x) + tcosx = 0. The value of t is __________.
2  
3  
4  
5 
f ’(x) = x(Sinx)’ + Sin(x)(x’)
= xCosx + Sinx ①
f ’’(x) = x (Cosx)’ + Cos (x)’+ Cos x
= x Sinx + 2Cosx ②
Given: f ’’(x) + f(x) + t Cosx = 0
Replace ① & ②,
xSinx + 2Cosx + xSinx + tCosx = 0
2Cosx + tCosx = 0
t = 2
Question 57 
A function f(x) is continuous in the interval [0,2]. It is known that f(0) = f(2) = 1 and f(1) = 1. Which one of the following statements must be true?
There exists a y in the interval (0,1) such that f(y) = f(y+1)  
For every y in the interval (0,1), f(y) = f(2y)  
The maximum value of the function in the interval (0,2) is 1  
There exists a y in the interval (0, 1) such that f(y) = f(2y) 
Since function f is continuous in [0, 2], therefore g would be continuous in [0, 1]
g(0) = 2, g(1) = 2
Since g is continuous and goes from negative to positive value in [0,1]. Therefore at some point g would be 0 in (0,1).
g=0 ⇒ f(y) = f(y+1) for some y in (0,1).
Apply similar logic to option D, Let g(y) = f(y) + f(2  y)
Since function f is continuous in [0, 2], therefore g would be continuous in [0, 1] (sum of two continuous functions is continuous)
g(0) = 2, g(1) = 2
Since g is continuous and goes from negative to positive value in [0, 1]. Therefore at some point g would be 0 in (0, 1).
There exists y in the interval (0, 1) such that:
g=0 ⇒ f(y) = f(2 – y)
Both A, D are answers.
Question 58 
Four fair sixsided dice are rolled. The probability that the sum of the results being 22 is X/1296. The value of X is ___________.
10  
11  
12  
13 
To get ‘22’ as Sum of four outcomes
x_{1} + x_{2} + x_{3} + x_{4} = 22
The maximum Sum = 6+6+6+6 = 24 which is near to 22
So, keeping three 6’s, 6+6+6+x = 22
x = 4 combination① = 6 6 6 4
Keeping two 6’s, 6+6+x_{1}+x_{2} = 22
x_{1}+x_{2} = 10 possible x’s (5, 5) only
combination② = 6 6 5 5
No. of permutation with 6664 = 4!/ 3! = 4
“ “ “ 6655 = 4!/ 2!2! = 6
Total = 4+6 = 10 ways out of 6×6×6×6 = 1296
Pnb (22) = 10/1296 ⇒ x = 10
Question 59 
A pennant is a sequence of numbers, each number being 1 or 2. An npennant is a sequence of numbers with sum equal to n. For example, (1,1,2) is a 4pennant. The set of all possible 1pennants is {(1)}, the set of all possible 2pennants is {(2), (1,1)}and the set of all 3pennants is {(2,1), (1,1,1), (1,2)}. Note that the pennant (1,2) is not the same as the pennant (2,1). The number of 10pennants is ________.
89  
90  
91  
92 
Single two: 211111111 ⇒ 9!/8!1! = 9 pennants
Two twos: 22111111 ⇒ 8!/6!2! = 28
Three twos: 2221111 ⇒ 7!/3!4! = 35
Four twos: 222211 ⇒ 6!/4!2! = 15
Five twos: 22222 ⇒ 1
Total = 89 pennants.
Question 60 
Let S denote the set of all functions f:{0,1}^{4 }→ {0,1}. Denote by N the number of functions from S to the set {0,1}. The value of log_{2}log_{2}N is ______.
16  
17  
18  
19 
{0,1}^{4} = {0,1}×{0,1}×{0,1}×{0,1} = 16
S = 2^{16}
N = 2^{S}
loglogN=loglog2^{S} = log S = log2^{16} = 16
Question 61 
Consider an undirected graph where selfloops are not allowed. The vertex set of G is {(i,j): 1 ≤ i ≤ 12, 1 ≤ j ≤ 12}. There is an edge between (a,b) and (c,d) if a  c ≤ 1 and b  d ≤ 1. The number of edges in this graph is __________.
506  
507  
508  
509 
If we observe the graph, it looks like a 12 by 12 grid. Each corner vertex has a degree of 3 and we have 4 corner vertices. 40 external vertices of degree 5 and remaining 100 vertices of degree 8.
From Handshaking theorem, sum of the degrees of the vertices is equal to the 2*number of edges in the graph.
⇒ (4*3) + (40*5) + (100*8) = 2*E
⇒ 1012 = 2*E
⇒ E = 506
Question 62 
An ordered tuple (d_{1}, d_{2}, ..., d_{n}) with d_{1} ≥ d_{2} ≥ ... d_{n} is called graphic if there exists a simple undirected graph with n vertices having degrees d_{1}, d_{2}, ..., d_{n} respectively. Which of the following 6tuples is NOT graphic?
(1, 1, 1, 1, 1, 1)  
(2, 2, 2, 2, 2, 2)  
(3, 3, 3, 1, 0, 0)  
(3, 2, 1, 1, 1, 0) 
A) (1, 1, 1, 1, 1, 1)
Yes, it is a graph.
We will see that option (C) is not graphic.
Question 63 
Which one of the following propositional logic formulas is TRUE when exactly two of p, q, and r are TRUE?
((p↔q)∧r)∨(p∧q∧∼r)  
(∼(p↔q )∧r)∨(p∧q∧∼r)  
((p→q)∧r)∨(p∧q∧∼r)  
(∼(p↔q)∧r)∧(p∧q∧∼r) 
Method2: directly check with one of {TTF, TFT, FTT} options.
As there are two T’s in each option, replace them and check with the third value.
Eg: Place p=q= T
(∼(p↔q)∧r)∨(p∧q∧∼r)
=(∼(T↔T)∧r)∨(T∧T∧∼r)
=(∼(T)∧r)∨(T∧∼r)
=(F∧r)∨(T∧∼r)
=(F)∨(∼r)
=∼r
This is true for r=F.
Similarly with p=r=T and q=F.
q=r=T and p=F
Option B is the answer.
Question 64 
Given the following schema:
employees(empid, firstname, lastname, hiredate, deptid, salary) departments(deptid, deptname, managerid, locationid)
You want to display the last names and hire dates of all latest hires in their respective departments in the location ID 1700. You issue the following query:
SQL> SELECT lastname, hiredate FROM employees WHERE (deptid, hiredate) IN ( SELECT deptid, MAX(hiredate) FROM employees JOIN departments USING(deptid) WHERE locationid = 1700 GROUP BY deptid);
What is the outcome?
It executes but does not give the correct result.  
It executes and gives the correct result.  
It generates an error because of pairwise comparison.  
It generates an error because the GROUP BY clause cannot be used with table joins in a subquery. 
Question 65 
Consider two processors P_{1} and P_{2} executing the same instruction set. Assume that under identical conditions, for the same input, a program running on P_{2} takes 25% less time but incurs 20% more CPI (clock cycles per instruction) as compared to the program running on P_{1}. If the clock frequency of P_{1} is 1GHz, then the clock frequency of P_{2} (in GHz) is _________.
1.6  
1.7  
1.8  
1.9 
Assume P_{1} takes 5 cycles for a program then P_{2} takes 20%more, means, 6 cycles.
P_{2} takes 25% less time, means, if P_{1} takes 5 ns, then P_{2} takes 3.75 ns.
Assume P_{2} clock frequency is x GHz.
P_{2} taken 6 cycles, so 6×10^{9}/x GH = 3.75, x = 1.6