GATE 2021 CSSet2
Question 1 
Listening to music has no effect on learning and a positive effect on physical exercise.  
Listening to music has a clear positive effect on physical exercise. Music has a positive effect on learning only in some students.  
Listening to music has a clear positive effect both on physical exercise and on learning.  
Listening to music has a clear positive effect on learning in all students. Music has a positive effect only in some students who exercise. 
From the first statement “Listening to music during exercise improves exercise performance and reduces discomfort. “ It is clear that listening to music has a positive effect on physical exercise.
From the statement “Scientists researched whether listening to music while studying can help students learn better and the results were inconclusive. “ it is clear that only on some students music has a positive effect.
Question 2 
A transparent square sheet shown above is folded along the dotted line. The folded sheet will look like _______.
Question 3 
as worse as  
as well as  
as better as  
as nicest as 
Question 4 
Vegetables  
Sharp  
Blunt  
Cut 
Question 5 
66  
22  
88  
110 
Given Initial ratio : 3:13:6
Total number of students initially = 3x+13x+6x = 22x
From the given question, we can write 3x+18 = 15y I
13x+18 = 35yII
6x+18 = 21yIII
I  II => 10X = 20Y
X=2YIV
Put IV in III => 6(2y) + 18 = 21y
12y + 18 = 21y
9y = 18
y = 2 V
Substitute V in I => 3x + 18 = 30
3x = 12
x = 4
Number of initial students = 22x = 22(4) = 88
Question 6 
The number of units of a product sold in three different years and the respective net profits are presented in the figure above. The cost/unit in Year 3 was ₹ 1, which was half the cost/unit in Year 2. The cost/unit in Year 3 was onethird of the cost/unit in Year 1. Taxes were paid on the selling price at 10%, 13% and 15% respectively for the three years. Net profit is calculated as the difference between the selling price and the sum of cost and taxes paid in that year.
The ratio of the selling price in Year 2 to the selling price in Year 3 is ______.
1:1  
3:4  
1:2  
4:3 
According to the given data:
Year Cost/unit Number of units Cost Price
1 ₹ 3 100 300
2 ₹ 2 200 400
3 ₹ 1 300 300
Cost Price = Cost/unit x Number of units
Net Profit = Selling Price  (Cost Price + (Tax% x selling price )
Year 2:
296 = SP  (400 + (13/100) x SP)
=>296 = 0.87SP  400
=> 0.87SP = 696
=> SP = ₹ 800
Year 3:
210 = SP  (300 + (15/100) x SP)
=> 210 = 0.85SP  300
=> 0.85SP = 510
=> SP = ₹ 600
The ratio of selling price in Year 2 to the selling price in year 3 = 800:600
= 4:3
Question 7 
A jigsaw puzzle has 2 pieces. One of the pieces is shown above. Which one of the given options for the missing piece when assembled will form a rectangle? The piece can be moved, rotated or flipped to assemble with the above piece.
Question 8 
2  
4  
8  
6 
Expand the given equation:
x^{2}+1/4  x x^{2 }9/4 +3x = x+2
=> 2 + 2x = x + 2
X = 4
Question 9 
Question 10 
Observation I: S is taller than R.
Observation II: Q is the shortest of all.
Observation III: U is taller than only one student.
Observation IV: T is taller than S but is not the tallest.
The number of students that are taller than R is the same as the number of students shorter than _______.
S  
P  
T  
R 
Number of students taller than R = Number of students shorter than S = 3
Question 11 
SYN bit = 1, SEQ number = X+1, ACK bit = 0, ACK number = Y, FIN bit = 0  
SYN bit = 0, SEQ number = X+1, ACK bit = 0, ACK number = Y, FIN bit = 1  
SYN bit = 1, SEQ number = Y, ACK bit = 1, ACK number = X+1, FIN bit = 0  
SYN bit = 1, SEQ number = Y, ACK bit = 1, ACK number = X, FIN bit = 0 
Q will send the SYN bit = 1 to the connection establishment.
Q Seq number will be Y different from X
ACK bit = 1 because sending the ACK
ACK number = X+1 (Next seq number id)
FIN bit = 0 (Because establishing the connection)
Question 12 
(0+1 (01*0)*1)*  
(0+11+10(1+00)*01)*  
(0*(1(01*0)*1)*)*  
(0+11+11(1+00)*00)* 
Transition table
0 
1 

>*q0 
q0 
q1 
q1 
q2 
q0 
q2 
q1 
q2 
DFA of divisible by 3
The regular expression will be
Three paths to reach to final state from initial state
Path 1: self loop of 0 on q0
Path 2: q0>q1>q0 hence 11
Path 3: q0>q1>q2>q1>q0 hence 10(1+00)*01
So finally the regular expression will be
(0+11+10(1+00)*01)*
Other regular expression is (if we consider two paths)
Path 1: Path 1: self loop of 0 on q0
Path 2: q0>q1>q2*>q1>q0
Hence regular expression
(0+1 (01*0)*1)*
Another regular expression is (if we consider only one path and remaining part is present inside this path as cycles)
q0>q1>q2>q1>q0
Another regular expression is
(0*(1(01*0)*1)*)*
So A,B, C are correct.
Option D generates string 11100 which is not accepted by FA hence wrong.
Question 13 
L={w x w^{R} x^{R }  w, x ∈ {0,1}* }  
L={w w^{R} x x^{R}  w, x ∈ {0,1}* }  
L={w x x^{R} w^{R}  w, x ∈ {0,1}* }  
L={w x w^{R}  w, x ∈ {0,1}* } 
Option A: L={w x w^{R} x^{R}  w, x ∈ {0,1}* }
This is not CFL as if we push “w” then “x” then we cannot match wR with “w” as top of stack contains x.
Option B: L={w w^{R} x x^{R}  w, x ∈ {0,1}* }
This is CFL. We non deterministically guess the middle of the string. So we push “w” then match with wR and again push x and match with xR
Option C: L={w x x^{R} w^{R}  w, x ∈ {0,1}* }
This is also CFL. We non deterministically guess the middle of the string. So we push “w” then push x and then match with xR and again match with wR
Option D: L={w x w^{R}  w, x ∈ {0,1}* }
This is a regular language (hence CFL). In this language every string start and end with same symbol (as x can expand).
Question 14 
OUT(S1) =IN(S2) U OUT(S2)  
OUT(S1) =IN(S1) U USE(S1)  
OUT(S1) =USE(S1) U IN(S2)  
OUT(S1) =IN(S2) 
Question 15 
698 
Total no. of records = 150000
Block size = 4096 bytes
Key size = 12 bytes
Record pointer size = 7 bytes
Question 16 
#include <stdio.h>
int foo(intx, int y, int q)
{
if ((x <= 0) && (y <= 0))
return q;
if (x <= 0)
return foo(x, yq, q);
if (y <= 0)
return foo(xq, y, q);
return foo(x, yq, q) + foo(xq, y, q);
}
int main()
{
int r = foo(15, 15, 10);
printf(“%d”, r);
return 0;
}
The output of the program upon execution is ______
60 
int foo(intx, int y, int q)
{
if ((x <= 0) && (y <= 0)) //if 1
return q;
if (x <= 0) //if 2
return foo(x, yq, q);
if (y <= 0) //if 3
return foo(xq, y, q);
return foo(x, yq, q) + foo(xq, y, q);
}
int main()
{
int r = foo(15, 15, 10);
printf(“%d”, r);
return 0;
}
Question 17 
Which of the following is/are correct about the graph?
For each pair of vertices u and v, there is a directed path from u to v.  
The graph does not have a strongly connected component.  
The graph does not have a topological order.  
A depthfirst traversal staring at vertex S classifies three directed edges as back edges. 
Option1: FALSE: There is no path from top right corner vertex to any other vertex
Option2: FALSE: A directed graph is called strongly connected if there is a path in each direction between each pair of vertices of the graph. As there is no path from the above vertex then this statement is wrong.
Option3: TRUE: This graph does have directed cycles, thus topological order can not be possible for according to topological definition.
Question 18 
exponent = 00000001 and mantissa = 00000000000000000000001  
exponent = 00000001 and mantissa = 00000000000000000000000  
exponent = 00000000 and mantissa = 00000000000000000000000  
exponent = 00000000 and mantissa = 00000000000000000000001 
The smallest biased exponent for the normalized number is E= 1.
The smallest Mantissa M = 000...0
The smallest positive normalized number = 1.M x 2 ^{E127}
= 1.0 x 2 ^{126 .}
= 2 ^{126}
Question 19 
In this question they given three main constraints
 The input array is in sorted order
 Use recursive binary search
 Worst case number of operations
If the array is in sorted order then the worst case time complexity is O(logn)
Ex: 10, 20, 30
The binary search approach is using either recursive or iterative method is
Step1: element = middle, the element is found and return the index.
Step2: element > middle, search for the element in the subarray starting from middle+1 index to n.
Step3: element < middle, search for element in the subarray starting from 0 index to middle 1.
Note: The worst case happens when we want to find the smallest/largest farthest node. So, it will not take more than O(logn) time.
Question 20 
Question 21 
R_{2}(Y), R_{1}(X), R_{3}(Z), R_{1}(Y), W_{1}(X), R_{2}(Z), W_{2}(Y), R_{3}(X), W_{3}(Z)
Consider the statements P and Q below:
P: S is conflictserializable.
Q: If T_{3}commits before T_{1}finishes, then S is recoverable.
Which one of the following choices is correct?
P is true and Q is false.  
Both P and Q are false.  
Both P and Q are true.  
P is false and Q is true. 
Question 22 
2 
Cache size = 2KB
Block size = 64 Bytes = 2^6 bytes. So the OFFSET is 6 bits long.
The TAG field is 22 bits. And the physical address is 32 bits.
Since it is given as a set associative cache, the physical address is divided as (TAG, SET, OFFSET).
From the given information we can find the SET number = 32  22  6 = 4 bits.
Using the 4 SET bits, the number of sets possible = 2^4 = 16.
Number of blocks in the cache = Cache size / Block size = 2KB / 64 = 2^11/2^6 = 2^5.
Number of sets in the cache = Number of blocks in the cache / Number of blocks in each set
Number of blocks in each set is also called the associativity.
16 = 2^5/associativity
Associativity = 2^5/16 = 2
Question 23 
Which one of the following options is correct about the recurrence T(n)?
Question 25 
z = x + 3 + y > f1 + y > f2;
for (i = 0; i < 200; i = i+2) {
if (z > i) {
p = p + x + 3;
q = q + y > f1;
} else {
p = p + y > f2;
q = q + x + 3;
}
}
Assume that the variable y points to a struct (allocated on the head) containing two fields f1 and f2, and the local variables x, y, z, p, q, and i are allotted registers. Common subexpression elimination (CSE) optimization is applied on the code. The number of addition and dereference operations (of the form y>f1 or y>f2) in the optimized code, respectively, are:
303 and 2  
303 and 102  
403 and 102  
203 and 2 
In compiler theory, common subexpression elimination is a compiler optimization that searches for instances for 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 example: Consider the following block of code
a=x+y+z;
r=p+q;
b=x+y+r;
The code after common subexpression elimination.
t=x+y;
a=t+z;
r=p+q;
b=t+r;
In the given code
z = x + 3 + y > f1 + y > f2;
for (i = 0; i < 200; i = i+2) {
if (z > i) {
p = p + x + 3;
q = q + y > f1;
} else {
p = p + y > f2;
q = q + x + 3;
}
}
X+3 is common subexpression, also y > f1 & y > f2 is found in first line itself so they are also like common subexpression.
Hence the code after common subexpression
t1=x+3; t2=y > f1 ; t3= y > f2;
z = t1 + t2 + t3;
for (i = 0; i < 200; i = i+2) {
if (z > i) {
p = p + t1;
q = q + t2;
} else {
p = p + t3;
q = q + t1;
}
}
Hence two dereference operations (of the form y>f1 or y>f2) in the optimized code.
The number of addition in the optimized code are:
Loop will execute for 100 times and in loop one addition (i+2)
So 100 additions.
Inside loop we have two additions (either in if block or in else block) so 200 additions inside loop
Hence 300 additions in loop (loop body as well as inside)
First 2 lines contains 3 additions
t1=x+3;
z = t1 + t2 + t3;
Hence total 303 additions.
So 303 and 2 are the answer.
Question 26 
80,000

Question 27 
#include<stdio.h>
int main() {
int arr[4][5];
int i, j;
for (i=0; i<4; i++){
for (j=0; j<5; j++){
arr[i][j] = 10*i + j;
}
}
printf (“%d”, *(arr[1] + 9));
return 0;
}
What is the output of the above program?
14  
30  
24  
20 
Question 28 
int SomeFunction (int x, int y)
{
if ((x == 1)  (y == 1)) return 1;
if (x == y) return x;
if (x > y) return SomeFunction (xy, y);
if (y > x) return SomeFunction (x, yx);
}
The value returned by SomeFunction (15, 255) is _______.
15 
Question 29 
10  
11  
9  
100 
s(P,Q) is the sum of dot products of vectors P and Q in each dimension. The 0 dot product indicates that the vectors must be orthogonal to each other.
In a ndimensional space, we have n axes orthogonal to each other. It is given that for every pair the dot product must be 0, then at most n vectors each mentioning each dimension can be considered. Thus for 10 dimensional space’s set of vectors ℒ , 10 mutually orthogonal vectors can be present.
Question 30 
S1 is false and S2 is true.  
Both S1 and S2 are false.  
Both S1 and S2 are true.
 
S1 is true and S2 is false. 
 A database table may have more than one foreign key, and each foreign key can have a different parent table. Hence, the statement I is incorrect.
 A foreign key is a set of attributes in a table that refers to the primary key of another table or to the primary key of the same table (selfreferential table). Hence, the statement II is also incorrect.
Question 31 

There are 8 ways to get ‘red’ in the fourth attempt of drawing
i.e., _ _ _ R these three gaps can be filled with B/R in 222=8 ways
The probability for case (1),
Question 32 
 Consider the following two statements about regular languages: S_{1}: Every infinite regular language contains an undecidable language as a subset. S_{2}: Every finite language is regular. Which one of the following choices is correct.?
Only S_{2}is true.  
Both S_{1}and S_{2}are true.  
Only S_{1}is true.  
Neither S_{1}nor S_{2}is true. 

S1 is true. We can solve this intuitively.
Suppose L=(a+b)* i.e, sigma*
We know that this is a regular language and any language is subset of this language.
As we know so many undecidable languages (not recursive languages) exist, hence S1 is true.
Take another example:
L=a* which is regular and infinite.
Take its subset L1=an  n> 0 and n is a set such that it cannot be generated by any algorithm
I.e, n is a set of natural numbers which does not have any algorithm which can generate this
So L1 is a undecidable language.
L2 is true as every finite language is regular.
Question 33 
Three address code  
Abstract Syntax Tree (AST)  
Symbol table  
Control Flow Graph (CFG) 

An intermediate representation is a representation of a program “between” the source and target languages. A good IR is one that is fairly independent of the source and target languages, so that it maximizes its ability to be used in a retargetable compiler.
Types of intermediate representation:
 Structured (Tree such as abstract syntax tree or Graph such as CFG, single static assignment)
 tuplebased, generally threeaddress code (quadruples)
Symbol table is not an intermediate representation of a source program. Symbol table is created in the first phase (lexical analysis phase and subsequently updated in later phases) and it stores the information about the occurrence of various entities such as variable names, function names, objects, classes, interfaces, etc.
Abstract syntax tree and three address code are well known representations of intermediate code.
CFG i.e., control flow graph is also a representation of intermediate code which represents the flow of control of the program. In CFG we break sequences of three address codes into basic blocks hence CFG is also a representation of intermediate code as it contains three address codes along with control flow representation with help of blocks and edges (arrows).
Question 34 
0x4243  
0x6665  
0x0001  
0x0100 
It is given that the unsigned integer is 2bytes long. It needs 4 hexadecimal digits.
We know the bigendian and littleendian computers differ in how the data is stored in memory.
In little endian machines, the last byte of binary representation of the multibyte datatype is stored first. On the other hand, in big endian machines, the first byte of binary representation of the multibyte datatype is stored first.
In the hexadecimal representation of the 2byte number on the little endian machine, the first two hexadecimal digits are for one byte and the last two hexadecimal digits are for the second byte. On the big endian machine it is the other way round.
It is given that the value in little endian representation is 255 more than the value in the big endian machine.
From the given options
A). In little endian = 0x4243 in binary (0100 0010 0100 0011) which has decimal value = 16963
On big endian = 0x4342 in binary (0100 0011 0100 0010) which has decimal value = 17218
Here the big endian value is higher than the little endian value. So this is not the correct option.
B). In little endian 0x6665 in binary (0110 0110 0110 0101) which has the decimal value = 26213
In big endian 0x6566 in binary (0110 0101 0110 0110) which has the decimal value = 25958
The difference = 26213  25958 = 255. So this is also the correct option.
C). In little endian 0x0001 in binary (0000 0000 0000 0001) which has the decimal value = 1.
In big endian 0x0100 in binary (0000 0001 0000 0000) has decimal value = 256.
But here also the big endian value is higher than the little endian. So this is not the correct option.
D). On the little endian machine for hexadecimal number 0x0100 in binary (0000 0001 0000 0000) which has decimal value = 256. On a big endian machine it is 0x 0001 in binary (0000 0000 0000 0001) which has decimal value = 1
The difference in value of little endian to big endian is 2561 = 255.
Hence 2, 4 are the correct options.
Question 35 
59049 
Question 36 
L U {01}  
L.L  
{0,1}*L  
L{01} 
Question 37 
Consider the following sequence of 8 instructions:
ADD, MUL, ADD, MUL, ADD, MUL, ADD, MUL
Assume that every MUL instruction is datadependent on the ADD instruction just before it and every ADD instruction (except the first ADD) is data dependent on the MUL instruction just before it. The Speedup is defined as follows:
Assume that every MUL instruction is datadependent on the ADD instruction just before it and every ADD instruction (except the first ADD) is datadependent on the MUL instruction just before it. The Speedup is defined as follows:
The Speedup achieved in executing the given instruction sequence on the pipelined processor (rounded to 2 decimal places) is ________.
1.875 
Question 38 
The number of strings of length 8 accepted by the above automaton is __________.
256 
So the DFA accepts all strings of length greater than equal to 3.
For 8 length strings we have 8 positions
_ _ _ _ _ _ _ _
For each position there are two possibilities 0 or 1.
So for 8 positions we have 28 possibilities = 256
Question 39 
f(w, 0, 0, z) = 1
f(1, x, 1, z) = x + z
f(w, 1, y, z) = wz + y
The number of literals in the minimal sumofproducts expression of f is __________.
6 
f(w,0,0,z)= 1 If x=y=0, then the sum of the corresponding minterms be 1.
The minterms with literals x’ and y’ are wx’y’z(9), w’x’y’z(1), wx’y’z’(8), w’x’y’z’(0) .
If x=y=0, then we get wz+w’z+wz’+w’z’ = 1.
f(1,x,1,z)= x+z.
The minterms with variables w and y in true form and x or z or both in true form.
The corresponding minterms are wx’yz(11), wxyz’(14), wxyz(15)
If w=1 and y=1, then we get x’z+xz’+xz= x+z.
f(w,1,y,z)= wz+y
The corresponding minterms are w’xyz’(6), w’xyz(7), wxyz’(14), wxyz(15), wxy’z(13).
If x=1, then we get w’yz’ + w’yz+ wyz’ + wyz+ wy’z = y + wz
So, the function f(w,x,y,z)= Σ(0,1,6,7, 8,9, 11, 13, 14, 15,).
Therefore, the kmap will be:
Therefore, the minimal expression will be: X’Y’ + WZ + XY
Thus, the number of literals will be 6.
Question 40 
function OWNRESOURCE(Resource R)
Acquire lock L // a global lock
if R is available then
Acquire R
Release lock L
else
if R is owned by another process P then
Terminate P, after releasing all resources owned by P
Acquire R
Restart P
Release lock L
end if
end if
end function
Which of the following choice(s) about the above scheme is/are correct?
The scheme ensures that deadlocks will not occur.  
The scheme may lead to livelock.  
The scheme violates the mutual exclusive property.  
The scheme may lead to starvation. 
(1) True,
The scheme ensures deadlock free operation, as there is no holdandwait condition possible.
(2) True,
The scheme may lead to priority inversion problems, and hence livelock is possible.
(3) False,
Mutual exclusion is satisfied as only one process can acquire and release locks at a time.
(4) True,
The scheme may lead to starvation. For example, the priority process can get scheduled repeatedly and keeps on killing the lower priority processes. Hence, a low priority process may strave.
Question 41 
4 
Question 42 
 If the first question is answered wrong, the student gets zero marks.
 If the first question is answered correctly and the second question is not answered correctly, the student gets the marks only for the first question.
 If both the questions are answered correctly, the student gets the sum of the marks of the two questions.
question  Probability of answering correctly  marks 
QuesA QuesB  0.8 0.5  10 20 
First QuesB and then QuesA. Expected marks 22.  
First QuesA and then QuesB. Expected marks 16.  
First QuesA and then QuesB. Expected marks 14.  
First QuesB and then QuesA. Expected marks 14. 
There are two ways to get marks.
1. Answering first question correctly, and second one wrongly
2. Answering first question and second question correctly.
There are two ways to answer the question paper. First A or First B.
In total we get 4 ways of answering the paper to get marks.
Note: Answering each question is independent, thus P(x intersection y) = P(x)*P(y)
P(Answering A correctly) =0.8, P( Answering A wrongly) = 10.8=0.2
P(Answering B correctly) =0.5, P( Answering B wrongly) = 10.5=0.5
Probability of Getting marks 
Marks 

First A correctly, B wrongly 
P(A correctly)*P(B wrongly) 
10+0 = 10 
First A correctly B correctly 
P(A correctly)*P(B Correctly) 
10+20 = 30 
First B correctly, A wrongly 
P(B correctly)*P(A wrongly) 
20+0=20 
First B correctly then A correctly 
P(B correctly)*P(A Correctly) 
20+10=30 
Expectation formula
E(X)=∑X*P(X)
Expectation for the order:A followed by B = 0.4*10 +0.4*30 = 16
Expectation for the order B followed by A = 0.1*20 + 0.4*30 = 14
As the target is to get maximum marks, the order A followed by B is the correct option
Question 43 
emp(empId, name, gender, salary, deptId)
Consider the following SQL query:
select deptId, count (*)
from emp
where gender = “female” and salary > (select avg(salary) from emp)
group by deptId;
The above query gives, for each department in the company, the number of female employees whose salary is greater than the average salary of
employees in the department  
female employees in the company  
employees in the company  
female employees in the department 
The given SQL query is:
Select deptId, count(*)
from emp
where gender = “female” and
group by deptId
 The inner query will return the average salary of the emp table.
 Hence, the given query will return the deptId wise count of female employees whose salary is greater than the average salary of the emp table.
Question 44 
111  
100  
101  
110 
Question 45 
S’ ⟶ S
S ⟶ S#cS
S ⟶ SS
S ⟶ S@
S ⟶ < S >
S ⟶ a
S ⟶ b
S ⟶ c
Let I_{0}=CLOSURE({S' ⟶.S}). The number of items in the set GOTO(GOTO(I0, <), <) is ____________.
8 
Question 46 
S_{1}:Read misses in a write through L1 cache do not result in writebacks of dirty lines to the L2.
S_{2}:Write allocate policy must be used in conjunction with write through caches and nowrite allocate policy is used with write back caches.
S_{1}is true and S_{2}is false  
S_{1}is false and S_{2}is false  
S_{1}is true and S_{2}is true  
S_{1}is false and S_{2}is true 
S1: In a write through cache the writing happens to both the L1 and L2 caches simultaneously. It is also given as the inclusive hierarchy. Here L1 is a subset of L2. So when there is a cache read miss in L1 we try to fetch the content from L2. If the block containing that missed word is dirty in the L1 cache, since it is a write through cache the same content would have also been written to the L2 cache also earlier itself. So there is no need to write back the dirty lines again to the L2 cache on a cache miss. Hence S1 is true.
S2: Generally nowrite allocate is used with write through cache and write allocate is used with write back cache. Hence S2 is false.
Question 47 
int x=0; // global
Lock L1; // global
main() {
create a thread to execute foo(); // Thread T1
create a thread to execute foo(); // Thread T2
wait for the two threads to finish execution;
print (x); }
foo() {
int y=0;
Acquire L1;
x = x + 1;
y = y + 1;
Release L1;
print (y);}
Which of the following statement(s) is/are correct?
At least one of P1 and P2 will print the value of x as 4.  
Both T1 and t2, in both the processes, will print the value of y as 1.  
Both P1 and P2 will print the value of x as2.  
At least one of the threads will print the value of y as 2. 
 True,
Execution order : P1>T1>T2; P2>T1>T2; P1print(x),P2print(x)  output is 4,4
 True,
y=y+1 can be treated as a critical section, and it is well synchronized by Acquire L1 and release L1.
 False, need not be true always.
 False,
Threads maintain their own copy of stack,and local variables (y) are stored on the stack.
Question 48 
S is a contradiction.  
The anecdote of S is logically equivalent to the consequent of S.  
S is a tautology.  
S is neither a tautology nor a contradiction. 
Question 49 
Question 50 
P⟶ QR
RS⟶ T
Which of the following functional dependencies can be inferred from the above functional dependencies?
PS ⟶ Q  
PS ⟶ T  
R ⟶ T  
P ⟶ R 
Question 51 
S_{1}: There exists a minimum weighted edge in G which is present in every minimum spanning tree of G.
S_{2}:If every edge in G has distinct weight, then G has a unique minimum spanning tree.
Which of the following options is correct?
S_{1}is false and S_{2}is true.
 
S_{1}is true and S_{2}is false.  
Both S_{1} and S_{2}are false.  
Both S_{1} and S_{2}are true. 
Statement1: FALSE: The given statement is not valid for all the cases because they are not mentioned, edge weights are in distinct or duplicate. So, we can take any random edge weights for the given statement.
Example:
Statement2: TRUE: Using the kruskal’s (or) prim's algorithm we get a unique MST when there is a unique edge weight.
Example:
Based on the above graph, we get the MST is
Question 52 
The next hop router for a packet from R to P is Y.  
The distance from R to Q will be stored as 7.  
The next hop router for a packet from R to Q is Z.  
The distance from R to P will be stored as 10. 
Given R gets the distance vector (3,2,5)
After the one iteration distance vector from X to P, Y to P, and Z to P is (7, 6, 5) respectively
The distance vector from R to P via X Y Z is (3+7, 2+6, 5+5) =(10, 8, 10)
So Take minimum distance from R to P which is 8 via Y
After the iteration distance vector from X to Q, Y to Q, Z to Q is ( 4, 6, 8) respectively
The distance vector from R to Q via X Y Z is (3+4, 2+6, 5+8) = (7, 8 13)
So Take minimum distance from R to Q which is 7 via X.
Question 53 
The page size is 4KB (1KB = 2^{10}bytes) and page table entry size at every level is 8 bytes. A process P is currently using 2GB (1GB = 2^{30}bytes) virtual memory which is mapped to 2GB of physical memory. The minimum amount of memory required for the page table of P across all levels is ________ KB.
8.01 
A system can support upto 2^39 bytes of Virtual address space. Three level paging is used with Level 1 (9 bits), Level 2 (9 bits) and Level 3 (9 bits) and page offset of 12 bits.
Page table entry is 8 bytes at every level. Therefore,
Level 3 page table size : 2^9 * 8bytes = 2^12 bytes. (Fits in one frame)
Level 2 page table size : 2^9 * 8bytes = 2^12 bytes. (Fits in one frame)
Level 1 page table size : 2^9 * 8bytes = 2^12 bytes. (Fits in one frame).
However, the process P has a virtual address space of 2^31 bytes. Thus, it is clear that the last level page table does not occupy the frame completely. Let x be the number of bits indexed in the last level.
Therefore, we can have (2^x) * (2^9) * (2^9)* (2^12) = 2^31 => x =1. Thus, the minimum size of page table for process P would be,
Page table size at level1 + Page table size at level2 + Page table size at level3 =
2^1 * 8bytes + 2^9 * 8bytes + 2^9 * 8bytes = (1026)*8 bytes = 8.01 KB
Question 54 
Implementing preemptive scheduling needed hardware support.  
Turnaround time includes waiting time  
Roundrobin policy can be used even when the CPU time required by each of the processes is not known apriori.  
The goal is to only maximize CPU utilization and minimize throughput. 
 True. Preemptive scheduling needs hardware support such as a timer
 True. Turnaround time = Burst time + Waiting time
 True, RR assigns qunatume to each process equally. Hence, it is not required to know burst size apriori
 False. Maximize CPU utilization and throughput, and minimize waiting time etc.
Question 55 
The sum of the qualityscores of all the vertices in the graph shown above is _________.
929 
Question 56 
135 
1 frames takes = Tt = L / B.w. => 1000 / 10^6 = 1 millisec
1000 frame Tt = 1000 x 1 millisec = 1 sec
In 1 sec, 1000 frames sends, which is 1 millisec per frame.
So, G = 1
Efficiency of Pure Aloha (η) = G x e^{2G}
where G = Number of requests per time slot willing to transmit.
e = Mathematical constant approximately equal to 2.718
So, η = 1 x 2.718(^{2 x 1)} = 0.1353
Therefore, In 1 sec1000 frames = 0.1353 x 1000 = 135.3(closest integer) =>135
Throughput => 135
Question 57 
1 
A={0,1,2} → BFS
The BFS traverse through level by level.
DFS:
B={0,1,3}
B={0,1,4}
B={0,2,6}
B={0,2,5}
The DFS starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
AB = 1
Note: The cardinality of set AB is 1.
Question 58 
Input sequence: 00100011000011100
Output sequence: 00000001000001100
A Mealy Machine is a state machine where both the next state and the output are functions of the present state and the current input.
The above mentioned circuit can be designed as a twostate Mealy machine. The states in the Mealy machine can be represented using Boolean values 0 and 1. We denote the current state, the next state, the next incoming bit, and the output bit of the Mealy machine by the variables s, t, b and y respectively.
What are the Boolean expressions corresponding to t and y in terms of s and b?
Question 59 
3 
Question 60 
#include<stdio.h>
#include<stdlib.h>
Struct Node{
int value;
struct Node *next;};
int main() {
struct Node *boxE, *head, *boxN; int index = 0;
boxE = head = (struct Node *) malloc(sizeof(struct Node));
head>value = index;
for (index = 1; index <= 3; index++) {
boxN = (struct Node *) malloc(sizeof(struct Node));
boxE>next = boxN;
boxN>value = index;
boxE = boxN; }
for (index = 0; index <= 3; index++) {
printf(“Value at index %d is %d\n”, index, head>value);
head = head>next;
printf(“Value at index %d is %d\n”, index+1, head>value); } }
Which one of the statements below is correct about the program?
Upon execution, the program creates a linkedlist of five nodes.  
It dereferences an uninitialized pointer that may result in a runtime error.  
Upon execution, the program goes into an infinite loop.  
It has a missing return which will be reported as an error by the compiler. 
One node is created with value 0.
Loop i runs from 1 to 3. Hence total 4 nodes will be created.
0 → 1 → 2 → 3 → NULL
When index =3, head =3
Head = Head → Next
Head → Value from printf will generate an error.
Question 61 
int main() {
Integer x;
return 0;
}
Which one of the following phases in a sevenphase C compiler will throw an error?
Syntax analyzer  
Lexical analyzer  
Semantic analyzer  
Machine dependent optimizer 
Question 62 
 For any two letters, the code assigned to one letter must not be a prefix of the code assigned to the other letter.
 For any two letters of the same frequency, the letter which occurs earlier in the dictionary order is assigned a code whose length is at most the length of the code assigned to the other letter.
21  
30  
23  
25 
Input String : abbccddeee
The character frequencies are
Character 
a 
b 
c 
d 
e 
Frequency 
1 
2 
2 
2 
3 
Binary Code 
? 
? 
? 
? 
? 
Question 63 
There exists a bijection from S_{1}to S_{2}.  
There does not exist a bijection from S_{1}to S_{2}.  
There exists a surjection from S_{1}to S_{2}.  
There does not exist an injunction from S_{1}to S_{2}. 
The number of functions from a set A to set B is B^A.
S2: B= 3, A= n^21 +1 = n^2.
we have number of functions 3^(n^2).
S1: there are n*n positions in a matrix of size nxn. Each can be filled with either 0 or 1 or 2 i,e, in 3^(n^2)
As there are equal number of elements on both sides, S1>S2 can be one one , onto as well bijection
Question 64 
The heap is nothing but a complete binary tree and uses linear search to find the elements.
In min heap, the parent key is less than or equal to (≤) the child keys. The maximum values should present in the farthest leaf node for the worst case time complexity.
To traverse all the elements in a heap will take O(n) time for the worst case because it uses the linear search to find the element.
Question 65 
15.49 