Gate 2017 set01
Question 1 

I. p ⇒ q
II. q ⇒ p
III. (¬q) ∨ p
IV. (¬p) ∨ q
I only  
I and IV only  
II only  
II and III only 
Construct Truth tables:
~p ⇒ ~q
II, III are equivalent to (~p) ⇒ (~q)
Method 2:
(I) p⇒q ≡ ~p∨q
(II) q⇒p ≡ ~q∨p
(III) (~q) ∨ p ≡ ~q∨p
(IV) (~p) ∨ p ≡ ~p∨q
Also, from question:
(~p) ⇒ (~q)
≡ p∨~q
So, (II) & (III) are equivalent to the statement given in question.
Question 2 
Consider the firstorder logic sentence F: ∀x(∃yR(x,y)). Assuming nonempty logical domains, which of the sentences below are implied by F?

I. ∃y(∃xR(x,y))
II. ∃y(∀xR(x,y))
III. ∀y(∃xR(x,y))
IV. ¬∃x(∀y¬R(x,y))
IV only  
I and IV only  
II only  
II and III only 
F: ∀x(∃yR(x,y)) (given)
: For all girls there exist a boyfriend
(x for girls and y for boys)
I: ∃y(∃xR(x,y))
: There exist some boys who have girlfriends.
(Subset of statement F, so True)
II: ∃y(∀xR(x,y))
: There exists some boys for which all the girls are girlfriend. (False)
III: ∀y(∃xR(x,y))
: For all boys exists a girlfriend. (False)
IV: ~∃x(∀y~R(x,y))
= ∀x(~∀y~R(x,y))
= ∀x(∃yR(x,y)) (∵ ~∀y=∃y, ~∃x=∀x)
(True)
Question 3 
a unique solution at x = J_{n} where J_{n} denotes a ndimensional vector of all 1  
no solution  
infinitely many solutions  
finitely many solutions 
AX = B
As given that
and c_{1}&c_{n} ≠ 0
means c_{0}a_{0} + c_{1}a_{1} + ...c_{n}a_{n} = 0, represents that a_{0}, a_{1}... a_{n} are linearly dependent.
So rank of 'A' = 0, (so if ‘B’ rank is = 0 infinite solution, ‘B’ rank>0 no solution) ⇾(1)
Another condition given here is, 'Σa_{i} = b',
so for c_{1}c_{2}...c_{n} = {1,1,...1} set, it is having value 'b',
so there exists a solution if AX = b →(2)
From (1)&(2), we can conclude that AX = B has infinitely many solutions.
Question 4 
Consider the following functions from positives integers to real numbers
The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:
Step1: Take n=2048 or 2^{11} (Always take n is very big number)
Step2: Divide functions into 2 ways
1. Polynomial functions
2. Exponential functions
Step3: The above functions are belongs to polynomial. So, simply substitute the value of n,
First compare with constant values.
→ 100 / 2048 = 0.048828125
→ 10 > 100/ 2048
→ log_{2} 2048 =11
→ √n = 45.25483399593904156165403917471
→ n = 2048
So, Option B is correct
Question 5 
(P)↔(ii), Q↔(iii), (R)↔(i)  
(P)↔(iii), Q↔(i), (R)↔(ii)  
(P)↔(ii), Q↔(i), (R)↔(iii)  
(P)↔(i), Q↔(ii), (R)↔(iii) 
(Q) QuickSort is a Divide and Conquer algorithm.
(R) Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem using Dynamic Programming.
Some important points regarding Greedy Vs Dynamic Programming
Greedy: →
It always gives polynomial time complexity
→ It is not an optimal
→ It always selects only either minimum or maximum among all possibilities
→ Ex: Dijkstra’s algorithm for SSSP, Optimal Merge Pattern, Huffman coding, Fractional knapsack problem, etc..,
Dynamic Programming:
→ It gives either polynomial or exponential time complexity.
→ It gives always an optimal result.
→ It checks all possibilities of a problem.
→ Ex: Longest Common sequence, Matrix chain Multiplication, Travelling sales Problem, etc..,
Question 6 
Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are:
Note: The height of a tree with a single node is 0.4 and 15 respectively  
3 and 14 respectively  
4 and 14 respectively  
3 and 15 respectively 
The height of a tree with single node is 0.
Minimum possible height is when it is a complete binary tree.
Maximum possible height is when it is a skewed tree left/right.
So the minimum and maximum possible heights of T are: 3 and 14 respectively.
Question 7 
2^{f} to 2^{i}  
2^{f} to (2^{i}  2^{f})  
0 to 2^{i}  
0 to (2^{i}  2^{f }) 
Number of bits in fraction part → fbits
Number of bits in integer part → (n – f) bits
Minimum value:
000…0.000…0 = 0
Maximum value:
= (2^{ nf }  1) + (1  2 ^{f}
= (2^{nf}  2 ^{f})
= (2^{i}  2 ^{ f })
Question 8 
Consider the C code fragment given below.
typedef struct node { int data; node* next; } node; void join(node* m, node* n) { node* p = n; while(p→next !=NULL) { p = p→next; } p→next=m; }
Assuming that m and n point to valid NULLterminated linked lists, invocation of join will
append list m to the end of list n for all inputs.  
either cause a null pointer dereference or append list m to the end of list n.  
cause a null pointer dereference for all inputs.  
append list n to the end of list m for all inputs. 
So have to consider both the cases.
⇾ 1. Lists are not null, invocation of JOIN will append list m to the end of list n.
m = 1, 2, 3
n = 4, 5, 6
After join, it becomes 4, 5, 6, 1, 2, 3, NULL.
⇾ 2. If lists are null, if the list n is empty, and itself NULL, then joining & referencing would obviously create a null pointer issue.
Hence, it may either cause a NULL pointer dereference or appends the list m to the end of list n.
Question 9 
When two 8bit numbers A_{7}...A_{0} and B_{7}...B_{0} in 2’s complement representation (with A_{0} and B_{0} as the least significant bits) are added using a ripplecarry adder, the sum bits obtained are S_{7}...S_{0} and the carry bits are C_{7}...C_{0}. An overflow is said to have occurred if
the carry bit C_{7} is 1  
all the carry bits (C_{7},…,C_{0}) are 1  
i.e., A_{7} = B_{7}
⇾ Overflow can be detected by checking carry into the sign bits (C_{in}) and carry out of the sign bits (C_{out}).
⇾ Overflow occurs iff A_{7} = B_{7} and C_{in} ≠ C_{out}
These conditions are equivalent to
Consider
Here A_{7} = B_{7} = 1 and S_{7} = 0
This happens only if C_{in} = 0
Carry out C_{out}=1 when
Similarly, in case of
C_{in}=1 and C_{out} will be 0.
Question 10 
Consider the following contextfree grammar over the alphabet Σ = {a, b, c} with S as the start symbol:

S → abScT  abcT
T → bT  b
Which one of the following represents the language generated by the above grammar?
{(ab)^{n} (cb)^{n}│n ≥ 1}  
{(ab)^{n} cb^{(m1 )} cb^{(m2 )}…cb^{(mn )}│n,m_{1},m_{2},…,m_{n} ≥ 1}  
{(ab)^{n} (cb^{m})^{n}│m,n ≥ 1}  
{(ab)^{n} (cb^{n})^{m}│m,n ≥ 1} 
S→ abScT  abcT, this production will generate equal number of “ab” and “c” and for every “abc” any number of b’s ( > 1) after “abc”.
For Ex:
Hence the language generated by the grammar is
L = {(ab)^{n} cb^{(m1 )} cb^{(m2 )}…cb^{(mn )}│n,m_{1},m_{2},…,m_{n} ≥ 1}
Question 11 
Consider the C struct defined below:
struct data { int marks [100]; char grade; int cnumber; }; struct data student;
The base address of student is available in register R1. The field student.grade can be accessed efficiently using
Postincrement addressing mode, (R1)+  
Predecrement addressing mode, (R1)  
Register direct addressing mode, R1  
Index addressing mode, X(R1), where X is an offset represented in 2’s complement 16bit representation 
{
int marks[100];
char grade;
int cnumber;
}; struct data student
Base Address of student is available in R1.
So student.grade can be accessed efficiently by Relative Indexed Addressing Mode.
It is clearly mentioned X is the offset address to be summed with Base Address of R1.
Hence Index Addressing mode X(R1), where X is an offset represented in 2’s complement 16bit representation.
⇾ Relative, Base Indexed & all subtypes of Indirect addressing modes are used with Arrays.
Question 12 
Consider the following intermediate program in three address code
p = a  b q = p * c p = u * v q = p + q
Which of the following corresponds to a static single assignment form of the above code?
In Static Single Assignment form (SSA) each assignment to a variable should be specified with distinct names.
We use subscripts to distinguish each definition of variables.
In the given code segment, there are two assignments of the variable p
p = ab
p = u*v
and two assignments of the variable q
q = p*c
q = p+q
So we use two variables p_{1}, p_{2} for specifying distinct assignments of p and q_{1}, q_{2} for each assignment of q.
Static Single Assignment form(SSA) of the given code segment is:
p_{1} = ab
q_{1} = p_{1} * c
p_{2} = u * v
q_{2} = p_{2} + q_{1}
Note:
As per options, given in GATE 2017 answer is B.
p_{3} = a  b
q_{4} = p_{3} * c
p_{4} = u * v
q_{5} = p_{4} + q_{4}
Question 13 
Consider the following C code:
#include <stdio.h> int *assignval(int *x, int val) { *x = val; return x; } void main ( ) { int *x = malloc(sizeof(int)); if(NULL == x) return; x = assignval(x, 0); if(x) { x = (int *)malloc(size of(int)); if(NULL == x) return; x = assignval(x, 10); } printf("%dn", *x); free(x); }
The code suffers from which one of the following problems:
compiler error as the return of malloc is not typecast approximately  
compiler error because the comparison should be made as x==NULL and not as shown  
compiles successfully but execution may result in dangling pointer  
compiles successfully but execution may result in memory leak 
In C++, we need to perform type casting, but in C Implicit type casting is done automatically, so there is no compile time error, it prints10 as output.
Option B:
NULL means address 0, if (a == 0) or (0 == a) no problem, though we can neglect this, as it prints 10.
Option C:
x points to a valid memory location. Dangling Pointer means if it points to a memory location which is freed/ deleted.
int*ptr = (int*)malloc(sizeof(int));
free(ptr); //ptr becomes a dangling pointer
ptr = NULL; //Removing Dangling pointers condition
Option D:
x is assigned to some memory location
int*x = malloc(sizeof(int));
→ (int*)malloc(sizeof(int)) again assigns some other location to x, previous memory location is lost because no new reference to that location, resulting in Memory Leak.
Hence, Option D.
Question 14 
Consider a TCP client and a TCP server running on two different machines. After completing data transfer, the TCP client calls close to terminate the connection and a FIN segment is sent to the TCP server. Serverside TCP responds by sending an ACK, which is received by the clientside TCP. As per the TCP connection state diagram (RFC 793), in which state does the clientside TCP connection wait for the FIN from the serverside TCP?
LASTACK  
TIMEWAIT  
FINWAIT1  
FINWAIT2 
i.e. waiting for the ACK for own FIN segment.
There are two possibilities here:
I. If Client receives ACK for its FIN then client will move to FINWAIT2 and will wait for matching FIN from server side.
After receiving the FIN from server, client will send ACK and move to TIMEWAIT state.
II. Client has sent FIN segment but didn’t get ACK till the time.
Instead of ACK, client received FIN from server side.
Client will acknowledge this FIN and move to CLOSE state.
Here Client will wait for the ACK for its own FIN.
After receiving ACK, client will move to TIMEWAIT state.
Here we encounter First Case.
So, the solution is (D).
Refer this TCP state transition diagram:
Question 15 
A sender S sends a message m to receiver R, which is digitally signed by S with its private key. In this scenario, one or more of the following security violations can take place.

(I) S can launch a birthday attack to replace m with a fraudulent message.
(II) A third party attacker can launch a birthday attack to replace m with a fraudulent message.
(III) R can launch a birthday attack to replace m with a fraudulent message.
Which of the following are possible security violations?
(I) and (II) only  
(I) only  
(II) only  
(II) and (III) only 
(I) Can the sender replace the message with a fraudulent message?
Yes, definitely because the sender will encrypt the message with its private key.
It can encrypt another message also with its private key.
(II) Can the third party send a fraudulent message?
No, because the third party doesn't know about the private key of the sender.
(III) Can receiver send the fraudulent message?
No, the receiver also doesn't know about the Private key of the sender.
So receiver also cannot send the fraudulent message.
Question 16 
The following functional dependencies hold true for the relational schema {V, W, X, Y, Z} :

V → W
VW → X
Y → VX
Y → Z
Which of the following is irreducible equivalent for this set of functional dependencies?
V→W V→X Y→V Y→Z  
V→W W→X Y→V Y→Z  
V→W V→X Y→V Y→X Y→Z  
V→W W→X Y→V Y→X Y→Z 
V → W, VW → X, Y → V, Y → X, Y→ Z
Step 2:
V → W, VW → X, Y → V, Y → X, Y→ Z
(V)^{+} = V ×
(VW)^{+} = VW ×
(Y)^{+} = YXZ
(Y)^{+} = YVW ×
(Y)^{+} = YVWX
Without Y → X, the closure of Y is deriving ‘X’ from the remaining attributes.
So, we can remove Y → X as its redundant.
Step 3:
V → W, VW → X, Y → V, Y → Z
(V)^{+} = VW, the closure of V is deriving W from the remaining FD’s.
So, W is redundant. We can remove it.
So, the final canonical form is
V→W, V→X, Y→V, Y→Z
⇾ So, option (A) is correct.
Question 17 
{R}  
{w}  
{w, y}  
{w, $} 
FOLLOW (Q) = FIRST (R)
FIRST (R) = {w, ϵ} >br> Since FIRST (R) = {ϵ}, so FOLLOW (Q) → {w} ∪ FIRST(S)
FIRST(S) = {y}
So, FOLLOW (Q) = {w, y}
Question 18 
global variables but not heap.  
heap but not global variables.  
neither global variables nor heap.  
both heap and global variables. 
Question 19 
Let X be a Gaussian random variable with mean 0 and variance σ^{2}. Let Y = max(X, 0) where max(a,b) is the maximum of a and b. The median of Y is __________.
0  
1  
2  
3 
Median is a point, where the probability of getting less than median is 1/2 and probability of getting greater than median is 1/2.
From the given details, we can simply conclude that, median is 0. (0 lies exactly between positive and negative values)
Question 20 
18  
19  
20  
21 
A tree, with 10 vertices, consists n  1, i.e. 10  1 = 9 edges.
Sum of degrees of all vertices = 2(#edges)
= 2(9)
= 18
Question 21 
Consider the Karnaugh map given below, where X represents “don’t care” and blank represents 0.
Assume for all inputs , the respective complements are also available. The above logic is implemented using 2input NOR gates only. The minimum number of gates required is _________.
1  
2  
3  
4 
As all variables and their complements are available we can implement the function with only one NOR Gate.
Question 22 
Consider the language L given by the regular expression (a+b)*b(a+b) over the alphabet {a,b}. The smallest number of states needed in deterministic finitestate automation (DFA) accepting L is _________.
4  
5  
6  
7 
After converting the NFA into DFA:
After converting the NFA into DFA:
Question 23 
Consider a database that has the relation schema EMP (EmpId, EmpName, and DeptName). An instance of the schema EMP and a SQL query on it are given below.
The output of executing the SQL query is ___________.
2.6  
2.7  
2.8  
2.9 
⇾ We start evaluating from the inner query.
The inner query forms DeptName wise groups and counts the DeptName wise EmpIds.
⇾ In inner query DeptName, Count(EmpId) is the alias name DeptName, Num.
So, the output of the inner query is,
The outer query will find the
Avg(Num) = (4+3+3+2+1)/5 = 2.6
Question 24 
Consider the following CPU processes with arrival times (in milliseconds) and length of CPU bursts (in milliseconds) as given below:
If the preemptive shortest remaining time first scheduling algorithm is used to schedule the processes, then the average waiting time across all processes is __________ milliseconds.
3  
4  
5  
6 
Question 25 
Consider a twolevel cache hierarchy with L1 and L2 caches. An application incurs 1.4 memory accesses per instruction on average. For this application, the miss rate of L1 cache is 0.1; the L2 cache experiences, on average, 7 misses per 1000 instructions. The miss rate of L2 expressed correct to two decimal places is __________.
0.05  
0.06  
0.07  
0.08 
For 1000 instructions total number of memory references = 1000 * 1.4 = 1400
These 1400 memory references are first accessed in the L1.
Since the miss rate of L1 is 0.1, for 1400 L1 references the number of misses = 0.1 * 1400 = 140
We know when there is a miss in L1 we next access the L2 cache.
So number of memory references to L2 = 140
It is given that there are 7 misses in L2 cache. Out of 140 memory references to L2 cache there are 7 misses.
Hence the miss rate in L2 cache = 7/140 = 0.05
Question 26 
Let G = (V, E) be any connected undirected edgeweighted graph. The weights of the edges in E are positive and distinct. Consider the following statements:

(I) Minimum Spanning Tree of G is always unique.
(II) Shortest path between any two vertices of G is always unique.
Which of the above statements is/are necessarily true?
(I) only  
(II) only  
both (I) and (II)  
neither (I) nor (II) 
Let us take an example
Step 1:
Using kruskal’s algorithm, arrange each weights in ascending order.
17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
Step 2:
Step 3:
17+18+20+21+22+23+26 = 147
Step 4:
Here, all the elements are distinct. So the possible MCST is 1.
StatementII: May or may not happen, please take an example graph and try to solve it. This is not correct always.
So, we have to pick most appropriate answer.
Question 27 
A multithreaded program P executes with x number of threads and used y number of locks for ensuring mutual exclusion while operating on shared memory locations. All locks in the program are nonreentrant, i.e., if a thread holds a lock l, then it cannot reacquire lock l without releasing it. If a thread is unable to acquire a lock, it blocks until the lock becomes available. The minimum value of x and the minimum value of y together for which execution of P can result in a deadlock are:
x = 1, y = 2  
x = 2, y = 1  
x = 2, y = 2  
x = 1, y = 1 
Here non reentrant process can’t own same lock multiple times, so if process tries to acquire already owned lock, will get blocked, and deadlock will happen.
From the above options x=1 (a single thread) and y=1 (a single lock) deadlock is possible when we consider given situations in question.
Question 28 
is 0  
is 1  
is 1  
does not exist 
If "x=1" is substituted we get 0/0 form, so apply LHospital rule
Substitute x=1
⇒ (7(1)^{6}10(1)^{4})/(3(1)^{2}6(1)) = (710)/(36) = (3)/(3) = 1
Question 29 
Let p, q and r be prepositions and the expression (p → q) → r be a contradiction. Then, the expression (r → p) → q is
a tautology  
a contradiction  
always TRUE when p is FALSE  
always TRUE when q is TRUE 
So r = F and (p→q) = T.
We have to evaluate the expression
(r→p)→q
Since r = F, (r→p) = T (As F→p, is always true)
The final expression is T→q and this is true when q is true, hence option D.
Question 30 
Let u and v be two vectors in R^{2} whose Euclidean norms satisfy u=2v. What is the value of α such that w = u + αv bisects the angle between u and v?
2  
1/2  
1  
1/2 
Let u, v be vectors in R^{2}, increasing at a point, with an angle θ.
A vector bisecting the angle should split θ into θ/2, θ/2
Means ‘w’ should have the same angle with u, v and it should be half of the angle between u and v.
Assume that the angle between u, v be 2θ (thus angle between u,w = θ and v,w = θ)
Cosθ = (u∙w)/(∥u∥ ∥w∥) ⇾(1)
Cosθ = (v∙w)/(∥v∥ ∥w∥) ⇾(2)
(1)/(2) ⇒ 1/1 = ((u∙w)/(∥u∥ ∥w∥))/((v∙w)/(∥v∥ ∥w∥)) ⇒ 1 = ((u∙w)/(∥u∥))/((v∙w)/(∥v∥))
⇒ (u∙w)/(v∙w) = (∥u∥)/(∥v∥) which is given that ∥u∥ = 2 ∥v∥
⇒ (u∙w)/(v∙w) = (2∥v∥)/(∥v∥) = 2 ⇾(3)
Given ∥u∥ = 2∥v∥
u∙v = ∥u∥ ∥v∥Cosθ
=2∙∥v∥^{2} Cosθ
w = u+αv
(u∙w)/(v∙w) = 2
(u∙(u+αv))/(v∙(u+αv)) = 2
(u∙u+α∙u∙v)/(u∙v+α∙v∙v) = 2a∙a = ∥a∥^{2}
4∥v∥^{2}+α∙2∙∥v∥^{2} Cosθ = 2(2∥v∥^{2} Cosθ+α∙∥v∥^{2})
4+2αCosθ = 2(2Cosθ+α)
4+2αCosθ = 4Cosθ+2α ⇒ Cosθ(uv)+2α4 = 0
42α = Cosθ(42α)
(42α)(Cosθ1) = 0
42α = 0
Question 31 
Both (I) and (II)  
(I) only  
(II) only  
Neither (I) nor (II) 
be a real valued, rank = 2 matrix.
a^{2}+b^{2}+c^{2}+d^{2} = 50
Square values are of order 0, 1, 4, 9, 16, 25, 36, …
So consider (0, 0, 5, 5) then Sum of this square = 0+0+25+25=50
To get rank 2, the 2×2 matrix can be
The eigen values are,
AλI = 0 (The characteristic equation)
λ(λ)25 = 0
λ^{2}25 = 0
So, the eigen values are within [5, 5], Statement I is correct.
The eigen values with largest magnitude must be strictly greater than 5: False.
So, only Statement I is correct.
Question 32 
A computer network uses polynomials over GF(2) for error checking with 8 bits as information bits and uses x^{3 }+ x + 1 as the generator polynomial to generate the check bits. In this network, the message 01011011 is transmitted as
01011011010  
01011011011  
01011011101  
01011011100 
= 1∙x^{3}+0∙x^{2}+1∙x^{1}+1∙x^{0}
=1011
Message =01011011
So, the message 01011011 is transmitted as
Question 33 
Consider a combination of T and D flipflops connected as shown below. The output of the D flipflop is connected to the input of the T flipflop and the output of the T flipflop is connected to the input of the D flipflop.
Initially, both Q_{0} and Q_{1} are set to 1 (before the 1^{st} clock cycle). The outputs
Question 34 
If G is a grammar with productions
where S is the start variable, then which one of the following strings is not generated by G?
abab  
aaab  
abbaa  
babba 
But the string “babba” can’t be generated by the given grammar.
The reason behind this is, we can generate any number of a’s with production S→ SaS, but for one “b” we have to generate one “a”, as the production which is generating “b” is also generating “a” together (S→ aSb and S→ bSa).
So in string “babba” the first and last “ba” can be generated by S→ bSa, but we can’t generate a single “b” in middle.
In other words we can say that any string in which number of “b’s” is more than number of “a’s” can’t be generated by the given grammar.
Question 35 
Consider the following two functions.
void fun1(int n) { void fun2(int n) { if(n == 0) return; if(n == 0) return; printf("%d", n); printf("%d", n); fun2(n  2); fun1(++n); printf("%d", n); printf("%d", n); } }
The output printed when fun1(5) is called is
53423122233445  
53423120112233  
53423122132435  
53423120213243 
In fun2, we increment (pre) the value of n, but in fun1, we are not modifying the value.
Hence increment in value in recursion (back).
Hence, 5 3 4 2 3 1 2 2 2 3 3 4 4 5.
Question 36 
Consider the C functions foo and bar given below:
int foo(int val) { int x = 0; while (val>0) { x = x + foo(val); } return val; } int bar(int val) { int x = 0; while (val>0) { x = x + bar(val1); } return val; }
Invocations of foo(3) and bar(3) will result in:
Return of 6 and 6 respectively.  
Infinite loop and abnormal termination respectively.  
Abnormal termination and infinite loop respectively.  
Both terminating abnormally. 
{
x = x + foo(val);
}
In this case foo(val) is same as foo(val) & val ;
Because the recursive function call is made without changing the passing argument and there is no Base condition which can stop it.
It goes on calling with the same value ‘val’ & the system will run out of memory and hits the segmentation fault or will be terminated abnormally.
The loop will not make any difference here.
while(val>0)
{
x = x + bar(val1);
}
bar(3) calls bar(2)
bar(2) calls bar(1)
bar(1) calls bar(0) ⇾ Here bar(0) will return 0.
bar(1) calls bar(0)
bar(1) calls bar(0)……..
This will continue.
Here is a problem of infinite loop but not abrupt termination.
Some compilers will forcefully preempt the execution.
Question 37 
Consider the contextfree grammars over the alphabet {a, b, c} given below. S and T are nonterminals.

G_{1}: S → aSbT, T → cTϵ
G_{2}: S → bSaT, T → cTϵ
The language L(G_{1}) ∩ L(G_{2}) is
Finite  
Not finite but regular  
ContextFree but not regular  
Recursive but not contextfree 
{ϵ, c, cc, ccc, … ab, aabb, aaabbb….acb, accb… aacbb, aaccbb, …}
Strings generated by G_{2}:
{ϵ, c, cc, ccc, … ba, bbaa, bbbaaa….bca, bcca… bbcaa, bbccaa, …}
The strings common in L (G_{1}) and L (G_{2}) are:
{ϵ, c, cc, ccc…}
So, L (G_{1}) ∩ L (G_{2}) can be represented by regular expression: c*
Hence the language L (G_{1}) ∩ L (G_{2}) is “Not finite but regular”.
Question 38 
Consider the following languages over the alphabet Σ = {a, b, c}.
Let L_{1} = {a^{n} b^{n} c^{m}│m,n ≥ 0} and L_{2} = {a^{m} b^{n} c^{n}│m,n ≥ 0}
Which of the following are contextfree languages?

I. L_{1} ∪ L_{2}
II. L_{1} ∩ L_{2}
I only  
II only  
I and II  
Neither I nor II 
Strings in L_{2} = {ϵ, a, aa, …., bc, bbcc,…., abc, aabc,…, abbcc, aabbcc, aaabbcc,..}
Strings in L_{1} ∪ L_{2} ={ϵ, a, aa, .., c, cc,.. ab, bc, …, aabb, bbcc,.., abc, abcc, aabc,…}
Hence (L_{1} ∪ L_{2}) will have either (number of a’s = equal to number of b’s) OR (number of b’s = number of c’s).
Hence (L_{1} ∪ L_{2}) is CFL.
Strings in L_{1} ∩ L_{2} = {ϵ, abc, aabbcc, aaabbbccc,…}
Hence (L_{1} ∩ L_{2}) will have (number of a’s = number of b’s = number of c’s)
i.e., (L_{1} ∩ L_{2}) = {a^{n}b^{n}c^{n}  n ≥ 0} which is CSL.
Question 39 
Let A and B be finite alphabets and let # be a symbol outside both A and B. Let f be a total function from A* to B*. We say f is computable if there exists a Turing machine M which given an input x in A*, always halts with f(x) on its tape. Let L_{f }denote the language {x # f(x)│x ∈ A* }. Which of the following statements is true:
f is computable if and only if L_{f} is recursive.  
f is computable if and only if L_{f} is recursively enumerable.  
If f is computable then L_{f} is recursive, but not conversely.  
If f is computable then L_{f} is recursively enumerable, but not conversely. 
Total function means for every element in domain, there must be a mapping in range.
Let us consider A= {a, b} and B = {0,1}
The concept of computing has been intuitively linked with the concept of functions.
A computing machine can only be designed for the functions which are computable.
The basic definition is:
Given a recursive language L and a string w over Σ*, the characteristic function is given by
The function “f” is computable for every value of "w".
However if the language L is not recursive, then the function f may or may not be computable.
Hence, f is computable iff L_{f} is recursive.
Question 40 
Recall that Belady’s anomaly is that the pagefault rate may increase as the number of allocated frames increases. Now, consider the following statements:

S1: Random page replacement algorithm (where a page chosen at random is replaced) suffers from Belady’s anomaly
S2: LRU page replacement algorithm suffers from Belady’s anomaly
Which of the following is CORRECT?
S1 is true, S2 is true  
S1 is true, S2 is false  
S1 is false, S2 is true  
S1 is false, S2 is false 
Page replacement algorithm suffers from Belady's anomaly when it is not a stack algorithm.
S1: Random page replacement algorithm is not a stack algorithm. So, S1 is true.
S2: LRU is a stack algorithm. Therefore, it doesn't suffer from Belady's anomaly. S2 is false.
Question 41 
Consider a database that has the relation schemas EMP(EmpId, EmpName, DeptId), and DEPT(DeptName, DeptId). Note that the DeptId can be permitted to a NULL in the relation EMP. Consider the following queries on the database expressed in tuple relational calculus.

(I) {t│∃u ∈ EMP(t[EmpName] = u[EmpName] ∧ ∀v ∈ DEPT(t[DeptId] ≠ v[DeptId]))}
(II) {t│∃u ∈ EMP(t[EmpName] = u[EmpName] ∧ ∃v ∈ DEPT(t[DeptId] ≠ v[DeptId]))}
(III) {t│∃u ∈ EMP(t[EmpName] = u[EmpName] ∧ ∃v ∈ DEPT(t[DeptId] = v[DeptId]))}
Which of the above queries are safe?
(I) and (II) only  
(I) and (III) only  
(II) and (III) only  
(I), (II) and (III) 
(I) Gives EmpNames who do not belong to any Department. So, it is going to be a finite number of tuples as a result.
(II) Gives EmpNames who do not belong to some Department. This is also going to have finite number of tuples.
(III) Gives EmpNames who do not belong to same Department. This one will also give finite number of tuples.
All the expressions I, II and III are giving finite number of tuples. So, all are safe.
Question 42 
In a database system, unique timestamps are assigned to each transaction using Lamport’s logical clock. Let TS(T_{1}) and TS(T_{2}) be the timestamps of transactions T_{1} and T_{2} respectively. Besides, T_{1} holds a lock on the resource R and T_{2} has requested a conflicting lock on the same resource R. The following algorithm is used to prevent deadlocks in the database system assuming that a killed transaction is restarted with the same timestamp.
if TS(T_{2})<TS(T_{1}) then T_{1} is killed else T_{2} waits.
Assume any transaction that is not killed terminates eventually. Which of the following is TRUE about the database system that uses the above algorithm to prevent deadlocks?
The database system is both deadlockfree and starvationfree.  
The database system is deadlockfree, but not starvationfree.  
The database system is starvationfree, but not deadlockfree.  
The database system is neither deadlockfree nor starvationfree. 
So, there will be no equal timestamps.
Lamport’s logical clock:
In this timestamps are assigned in increasing order only.
According to the given algorithm,
TS(T_{2}) < TS(T_{1})
then T_{1} is killed
else
T_{2} will wait
So, in both the cases, it will be deadlock free and there will be no starvation.
Question 43 
Consider the following grammar:
stmt → if expr then expr else expr; stmt  ȯ expr → term relop term  term term → id  number id → a  b  c number → [09]
where relop is a relational operator (e.g., <, >, …), ȯ refers to the empty statement, and if, then, else are terminals.
Consider a program P following the above grammar containing ten if terminals. The number of control flow paths in P is ________. For example, the program
if e_{1} then e_{2} else e_{3}
has 2 control flow paths, e_{1} → e_{2} and e_{1} → e_{3}.
1024  
1025  
1026  
1027 
if
if
:
:
:
(keep doing 10 times to get 10 'if')
We know that every if statement has 2 control flows as given in question. Hence,
We have 2 control flow choices for 1st 'if'
We have 2 control flow choices for 2nd 'if'
:
:
:
We have 2 control flow choices for 10th 'if'
Since all the choices are in one single structure or combination, so total choices are
2 × 2 × 2 × ........ 10 times = 2^{10} = 1024
Question 44 
In a RSA cryptosystem, a participant A uses two prime numbers p = 13 and q = 17 to generate her public and private keys. If the public key of A is 35, then the private key of A is _________.
11  
12  
13  
14 
Given, p=13, q=17, e=35 (Public key), d=? (Private key)
As per RSA Algorithm; following steps:
Step 1: Find n = p×q = 13×17 = 221
Step 2: Find ∅(n) = (p1)×(q1) = 12×16 = 192
Step 3: d×e mod ∅(n) = 1 ⇒ (d = e^{(1)} mod ∅(n))
or
d×e = 1 mod ∅(n)
⇒ d×35 mod 192 = 1
Question 45 
The value of parameters for the StopandWait ARQ protocol are as given below:
Bit rate of the transmission channel = 1 Mbps. Propagation delay from sender to receiver = 0.75 ms. Time to process a frame = 0.25 ms. Number of bytes in the information frame = 1980. Number of bytes in the acknowledge frame = 20. Number of overhead bytes in the information frame = 20.
Assume that there are no transmission errors. Then, the transmission efficiency (expressed in percentage) of the StopandWait ARQ protocol for the above parameters is _________ (correct to 2 decimal places).
89.33%  
89.34%  
89.35%  
89.36% 
B = 1Mbps, L = 1980Bytes, Overhead = 20Bytes
T_{Proc} = 0.25ms, L_{Ack} = 20Bytes
T_{p}=0.75ms
Total Data size(L) = (L + overhead) = 1980+20 = 2000Bytes
Efficiency of Stop & Wait ARQ?
T_{t} = L/B = 2000Bytes/1Mbps = (2000×8bits)/(10^{6} b/s) = 16msec
T_{Ack} = L_{Ack}/B = (20×8bits)/(10^{6} bits/sec) = 0.16msec
∴ In Stop and Wait ARQ, efficiency
ƞ = T_{t}/(T_{t}+T_{Ack}+2T_{p}+T_{Proc}) = 16ms/(16+0.16+2×0.75+0.25ms) = 16ms/17.91ms = 0.8933
Question 46 
Consider a database that has the relation schema CR(StudentName, CourseName). An instance of the schema CR is as given below.
The following query is made on the database.
T1 ← π_{CourseName}(σ_{StudentName='SA'}(CR)) T2 ← CR ÷ T1
The number of rows in T2 is ____________.
4  
5  
6  
7 
The σ_{StudentName = 'SA'}(CR) will produce the following
⇾ The result of T1 ← π_{CourseName}(σ_{StudentName='SA'}(CR)) is
(2) T2 ← CR÷T1
⇾ We see that SA is enrolled for CA, CB and CC.
⇾ T2 will give the StudentNames those who have enrolled for all the CA, C, CC courses. So, the following Students are enrolled for the given 3 courses.
⇾ So, the output of T2 will have 4 rows.
Question 47 
The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is _________.
271  
272  
273  
274 
Let A = number divisible by 3
B = numbers divisible by 5
C = number divisible by 7
We need to find “The number of integers between 1 and 500 that are divisible by 3 or 5 or 7" i.e., A∪B∪C
We know,
A∪B∪C = A+B+CA∩BA∩CB∩C+A∩B
A = number of integers divisible by 3
[500/3 = 166.6 ≈ 166 = 166]
B = 100
[500/5 = 100]
C = 71
[500/7 = 71.42]
A∩B = number of integers divisible by both 3 and 5 we need to compute with LCM (15)
i.e.,⌊500/15⌋ ≈ 33
A∩B = 33
A∩C = 500/LCM(3,7) 500/21 = 23.8 ≈ 28
B∩C = 500/LCM(5,3) = 500/35 = 14.48 ≈ 14
A∩B∩C = 500/LCM(3,5,7) = 500/163 = 4.76 ≈ 4
A∪B∪C = A+B+CA∩BA∩CB∩C+A∩B∩C
= 166+100+71332814+4
= 271
Question 48 
Let A be an array of 31 numbers consisting of a sequence of 0’s followed by a sequence of 1’s. The problem is to find the smallest index i such that A[i] is 1 by probing the minimum number of locations in A. The worst case number of probes performed by an optimal algorithm is _________.
5  
6  
7  
8 
→ As in this array sequence of 0’s is followed by sequence of 1’s, the array is sorted. We can apply binary search directly without sorting it.
So number of probes = ceil(log_{2} 31) = 4.954196310386876
⇒ here we are using ceiling so it becomes 5
Question 49 
Consider a RISC machine where each instruction is exactly 4 bytes long. Conditional and unconditional branch instructions use PCrelative addressing mode with Offset specified in bytes to the target location of the branch instruction. Further the Offset is always with respect to the address of the next instruction in the program sequence. Consider the following instruction sequence
If the target of the branch instruction is i, then the decimal value of the Offset is ___________.
16  
17  
18  
19 
Program counter Relative Addressing Mode
⇾ Assuming the first instruction starts at address zero
Offset should go from Address 16 to Address 0
⇒ Offset = 0 – 16 = (16) ⇾ Final answer
Question 50 
Instruction execution in a processor is divided into 5 stages, Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Execute (EX), and Write Back (WB). These stages take 5, 4, 20, 10 and 3 nanoseconds (ns) respectively. A pipelined implementation of the processor requires buffering between each pair of consecutive stages with a delay of 2 ns. Two pipelined implementations of the processor are contemplated:

(i) a naive pipeline implementation (NP) with 5 stages and
(ii) an efficient pipeline (EP) where the OF stage is divided into stages OF1 and OF2 with execution times of 12 ns and 8 ns respectively.
The speedup (correct to two decimal places) achieved by EP over NP in executing 20 independent instructions with no hazards is _________.
1.51  
1.52  
1.53  
1.54 
The stage delays are 5, 4, 20, 10 and 3. And buffer delay = 2ns
So clock cycle time = max of stage delays + buffer delay
= max(5, 4, 20, 10,3)+2
= 20+2
= 22ns
Execution time for ninstructions in a pipeline with kstages = (k+n1) clock cycles
= (k+n1)* clock cycle time
In this case execution time for 20 instructions in the pipeline with 5stages
= (5+201)*22ns
= 24*22
= 528ns
Efficient Pipeline implementation:
OF phase is split into two stages OF1, OF2 with execution times of 12ns, 8ns
New stage delays in this case = 5, 4, 12, 8, 10, 3
Buffer delay is the same 2ns.
So clock cycle time = max of stage delays + buffer delay
= max(5, 4, 12, 8, 10,3) + 2
= 12+2
= 14ns
Execution time = (k+n1) clock cycles
= (k+n1)* clock cycle time
In this case no. of pipeline stages, k = 6
No. of instructions = 20
Execution time = (6+201)*14 = 25*14 = 350ns
Speed up of Efficient pipeline over native pipeline
= Naive pipeline execution time / efficient pipeline execution time
= 528 / 350
≌ 1.51
Question 51 
Consider a 2way set associative cache with 256 blocks and uses LRU replacement. Initially the cache is empty. Conflict misses are those misses which occur due to contention of multiple blocks for the same cache set. Compulsory misses occur due to first time access to the block. The following sequence of accesses to memory blocks
(0, 128, 256, 128, 0, 128, 256, 128, 1, 129, 257, 129, 1, 129, 257, 129)
is repeated 10 times. The number of conflict misses experienced by the cache is __________.
76  
79  
80  
81 
If a block is accessed once and then before its second access if there are kunique block accesses and the cache size is less than k, and in that case if the second access is amiss then it is capacity miss. In this case the cache doesn't have the size to hold all the kunique blocks that came and so when the initial block came back again it is not in the cache because capacity of the cache is less than the unique block accesses k. Hence it is capacity miss.
If a block is accessed once and then before its second access if there are kunique block accesses and the cache size is greater than k, and in that case if the second access is a miss then it is conflict miss. In this case the cache can hold all the kunique blocks that came and even then when the initial block came back again it is not in the cache because it got replaced, then it is conflict miss.
LRU will use the function xmod128
Cache size = 256 Bytes
2 way set associative cache
So, no. of cache sets = 256/2 = 128
Blue → Compulsory miss
Red → Conflict miss
At the end of first round we have 4, compulsory misses & 4 conflict misses.
Similarly, if we continue from Round2 to last round, in every round we will get 8 conflict misses.
Total conflict misses = 4+9(8) = 4+72 = 76 (conflict misses)
Question 52 
Consider the expression (a1)*(((b+c)/3)+d)). Let X be the minimum number of registers required by an optimal code generation (without any register spill) algorithm for a load/store architecture, in which (i) only load and store instructions can have memory operands and (ii) arithmetic instructions can have only register or immediate operands. The value of X is ___________.
2  
3  
4  
5 
Question 53 
#include <stdio.h> #include <string.h> void printlength (char*s, char*t) { unsigned int c = 0; int len = ((strlen(s)  strlen(t)) > c) ? strlen(s):strlen(t); printf("%d\n", len); } void main () { char*x = "abc"; char*y = "defgh"; printlength(x,y); }Recall that strlen is defined in string.h as returning a value of type size_t, which is an unsigned int. The output of the program is _________.
3  
4  
5  
6 
{
char*x = "abc";
char*y = "defgh";
printlength(x,y);
}
printlength(char*3, char*t)
{
unsigned int c = 0;
int len = ((strlen(s)  strlen(t))> c) ? strlen(s) : strlen(t);
printf("%d", len);
}
Here strlen(s)  strlen(t) = 3  5 = 2
But in C programming, when we do operations with two unsigned integers, result is also unsigned. (strlen returns size_t which is unsigned in most of the systems).
So this result '2' is treated as unsigned and its value is INT_MAX2.
Now the comparison is in between large number & another unsigned number c, which is 0.
So the comparison returns TRUE here.
Hence (strlen(s)  strlen(t))>0 will return TRUE, on executing, the conditional operator will return strlen(s)
⇒ strlen(abc) = 3
Question 54 
A cache memory unit with capacity of N words and block size of B words is to be designed. If it is designed as a direct mapped cache, the length of the TAG field is 10 bits. If the cache unit is now designed as a 16way setassociative cache, the length of the TAG field is ___________ bits.
14  
15  
16  
17 
(Tag bits + bits for block number + bits for block offset)
With block size being B words no. of bits for block offset = log (B)
Because the cache capacity is N words and each block is B words, number of blocks in cache = N / B
No. of bits for block number = log (N/B)
So, the physical address in direct mapping case
= 10 + log (N/B) + log (B)
= 10 + log (N) – log B + log B
= 10 + log (N)
If the same cache unit is designed as 16way set associative, then the physical address becomes
(Tag bits + bits for set no. + Bits for block offset)
There are N/B blocks in the cache and in 16way set associative cache each set contains 16 blocks.
So no. of sets = (N/B) / 16 = N / (16*B)
Then bits for set no = log (N/16B)
Bits for block offset remain the same in this case also. That is log (B).
So physical address in the set associative case
= tag bits + log (N/16*B) + log B
= tag bits + log (N) – log (16*B) + log B
= tag bits + log (N) – log 16 – log B + log B
= tag bits + log N – 4
The physical address is the same in both the cases.
So, 10 + log N = tag bits + log N – 4
Tag bits = 14
So, no. of tag bits in the case 16way set associative mapping for the same cache = 14.
Question 55 
The output of executing the following C program is __________.
#include<stdio.h> int total (int v) { static int count=0; while(v) { count += v&1; v ≫= 1; } return count; } void main() { static int x = 0; int i = 5; for(; 1> 0; i) { x = x + total(i); } printf("%d\n", x); }
23  
24  
25  
26 
Question 56 
After RajendraChola returned from his voyage to Indonesia, he _________ to visit the temple in Thanjavur.
was wishing  
is wishing  
wished  
had wished 
After Rajendrachola returned from his voyage to Indonesia, he wished to visit the temple in Tanjavur.
Question 57 
Research in the workplace reveals that people work for many reason __________.
money beside  
beside money  
money besides  
besides money 
Here we are using besides preposition "in addition to".
Question 58 
Rahul, Murali, Srinivas and Arul are seated around a square table. Rahul is sitting to the left of Murali,Srinivas is sitting to the right of Arul. Which of the following pairs are seated opposite each other?
Rahul and Murali  
Srinivas and Arul  
Srinivas and Murali  
Srinivas and Rahul 
Srinivas and Murali and Arul and Rahul are opposite to each other.
They face away from the center of table
Even in this case,
Srinivas and Murali and Arul and Rahul are opposite to each other.
Question 59 
Find the smallest number y such that y × 162 is a prefect cube.
24  
27  
32  
36 
⇒ 162 = 2×3×3×3×3 = 3^{3}×(2×3)
For (2×3) to be a perfect cube, it should be multiplied by (2^{2}×3^{2})
∴ Required number = y = 2^{2}×3^{2} = 36
Question 60 
0.3^{k}  
0.6^{k}  
0.7^{k}  
0.9^{k} 
Total no.of possibilities = (10)^{k}
Required probability = (7)^{k} / (10)^{k} = 0.7^{k}
Question 61 
“The hold of the nationalist imagination on our colonial past is such that anything inadequately or improperly nationalist is just not history.”
Which of the following statements best reflects the author’s opinion?
Nationalists are highly imaginative.  
History is viewed through the filter of nationalism.  
Our colonial past never happened.  
Nationalism has to be both adequately and properly imagined. 
That represents the history of nationalism.
Question 62 
Six people are seated around a circular table. There are atleast two men and two women. There are at least three righthanded persons. Every woman has a lefthanded person to her immediate right. None of the women are righthanded. The number of women at the table is
2  
3  
4  
Cannot be determined 
Atleast three right handed persons.
None of the women are righthanded.
⇒ All the righthanded persons are men. Every woman has a lefthanded person to her immediate right.
⇒ For this to happen, there must be three lefthandedpersons and one of them should be a male.
As three persons are righthanded and those being men.
The number of women at the table = 2
Question 63 
the maximum of x and y  
the minimum of x and y  
1  
none of the above 
CaseI: x > y
⇒ x  y = x  y
Expression ⇒ (x + y)  (x  y) / 2 = y
In this case value of expression is minimum of y.
CaseII: x < y
⇒ x  y = (x  y)
Expression ⇒ (x + y)  (x  y) / 2
⇒ (x + y)  [(x  y)]/2 ⇒ x
In this case value of expression is minimum of x.
Finally, the value of expression is minimum of x & y.
Question 64 
Arun, Gulab, Neel and Shweta must choose one shirt each from a pile of four shirts coloured red, pink, blue and white respectively. Arun dislikes the colour red and Shweta dislikes the colour white. Gulab and Neel like all the colours. In how many different ways can they choose the shirts so that no one has a shirt with a colour he or she likes?
21  
18  
16  
14 
Number of ways Arun chooses red or Shweta chooses white
= Number of ways Arun chooses red + Number of ways Shweta chooses white  Number of ways Arun chooses red and Shweta chooses white
= ^{3}P_{3} + ^{3}P_{3}  ^{2}P_{2}
= 3! + 3!  2!
= 10
∴ Required number of ways = 24  10 = 14
Question 65 
A contour line joins locations having the same height above the mean sea level. The following is a contour plot of a geographical region. Contour lines are shown at 25 m intervals in this plot. If in a flood, the water level rises to 525 m, which of the villages P, Q, R, S, T get submerged?
P, Q  
P, Q, T  
R, S, T  
Q, R, S 
∴ From the plot,
P=575m
Q=525m
R=475m
S=425m
T=500m
For a village to be submerged, the water level should rise to level greater than the village.
If water level rises to 525m, villages which are at heights below 525m, get submerged.
Here, R, S, T get submerged.