GATE 2006
Question 1 
Consider the polynomial p(x) = a_{0} + a_{1}x + a_{2}x^{2} + a_{3}x^{3}, where a_{i} ≠ 0, ∀_{i}. The minimum number of multiplications needed to evaluate p on an input x is:
3  
4  
6  
9 
p(x) = a_{0} + a_{1}x + a_{2}x^{2} + a_{3}x^{3} where a_{i}≠0
This can be written as
p(x) = a_{0} +x( a_{1} + a_{2}x + a_{3}x^{2})=a_{0}+(a_{1}+(a_{2}+a_{3}x)x)x
Total no. of multiplications required is 3
i.e., a_{3}x = K.....(i)
(a_{2}+K)x = M..... (ii)
(a_{1}+M)x=N...... (iii)
Question 2 
Let X, Y, Z be sets of sizes x, y and z respectively. Let W = X×Y and E be the set of all subsets of W. The number of functions from Z to E is:
Z^{2}^{xy}  
Z×2^{xy}  
Z^{2}^{x+y}  
2^{xyz} 
A set ‘P’ consists of m elements and ‘Q’ consists of n elements then total number of function from P to Q is m^{n}.
⇒ E be the no. of subsets of W = 2^{w} = 2^{xxy} = 2^{xy}
No. of function from Z to E is = (2xy)^{z} = (2xy)^{z} = 2^{xyz}
Question 3 
The set {1, 2, 3, 5, 7, 8, 9} under multiplication modulo 10 is not a group. Given below are four plausible reasons. Which one of them is false?
It is not closed  
2 does not have an inverse  
3 does not have an inverse  
8 does not have an inverse 
Option A:
It is not closed under multiplication. After multiplication modulo (10) we get ‘0’. The ‘0’ is not present in the set.
(2*5)%10 ⇒ 10%10 = 0
Option B:
2 does not have an inverse such as
(2*x)%10 ≠ 1
Option C:
3 have an inverse such that
(3*7)%10 = 1
Option D:
8 does not have an inverse such that
(8*x)%10 ≠ 1
Question 4 
A relation R is defined on ordered pairs of integers as follows: (x,y) R(u,v) if x < u and y > v. Then R is: Then R is:
Neither a Partial Order nor an Equivalence Relation  
A Partial Order but not a Total Order  
A Total Order  
An Equivalence Relation 
i) Symmetric
ii) Reflexive
iii) Transitive
If a relation is partial order relation then it must be
i) Reflexive
ii) Antisymmetric
iii) Transitive
If a relation is total order relation then it must be
i) Reflexive
ii) Symmetric
iii) Transitive
iv) Comparability
Given ordered pairs are (x,y)R(u,v) if (x
Here <, > are using while using these symbol between (x,y) and (y,v) then they are not satisfy the reflexive relation. If they uses (x<=u) and (y>=u) then reflexive relation can satisfies.
So, given relation cannot be a Equivalence. Total order relation or partial order relation.
Question 5 
For which one of the following reasons does Internet Protocol (IP) use the timeto live (TTL) field in the IP datagram header?
Ensure packets reach destination within that time  
Discard packets that reach later than that time  
Prevent packets from looping indefinitely  
Limit the time for which a packet gets queued in intermediate routers 
Question 6 
Consider three CPUintensive processes, which require 10, 20 and 30 time units and arrive at times 0, 2 and 6, respectively. How many context switches are needed if the operating system implements a shortest remaining time first scheduling algorithm? Do not count the context switches at time zero and at the end.
1  
2  
3  
4 
Total no.of context switches is 2.
Question 7 
Consider the following grammar.
S → S * E S → E E → F + E E → F F → id
Consider the following LR(0) items corresponding to the grammar above.
(i) S → S * .E (ii) E → F. + E (iii) E → F + .E
Given the items above, which two of them will appear in the same set in the canonical setsofitems for the grammar?
(i) and (ii)  
(ii) and (iii)  
(i) and (iii)  
None of the above 
Question 8 
You are given a free running clock with a duty cycle of 50% and a digital waveform f which changes only at the negative edge of the clock. Which one of the following circuits (using clocked D flipflops) will delay the phase of f by 180°?
50% of duty cycle means, the wave is 1 for half of the time and 0 for the other half of the time. It is a usual digital signal with 1 and 0.
The waveform f changes for every negative edge, that means f value alters from 1 to 0 or 0 to 1 for every negative edge of the clock.
Now the problem is that we need to find the circuit which produces a phase shift of 180, which means the output is 0 when f is 1 and output is 1 when f is 0.
Like the below image.
Now to find the answer we can choose elimination method.
F changes for negative edge, so that output too should change at negative edge. i.e if f becomes 0, then at the same time output should become 1, vice versa.
So, whenever input changes, at the same point of time output too should change. As input changes on negative edge, the output should be changed at negative edge only.
To have the above behaviour, the second D flipflop which produces the final output should be negative edge triggered. because whatever the 2nd flipflop produces, that is the output of the complete circuit.
So, we can eliminate option a, d.
Now either b or c can be answer.
How the flipflop chain works in option b and c is as below.
—> F changes at negative edge.
—> But flipflop1 responds at next positive edge.
—> After this flipflop2 responds at next negative edge.
That means flipflop2 produces the same input which is given to flipflop now after a positive edge and a negative edge, that means a delay of one clock cycle, which is 180 degrees phase shift for the waveform of f.
Option b) we are giving f’, so that the output is f’ with 180 degrees phase shift.
Option c) we are giving f, so that the output is f with 180 degrees phase shift.
Hence option C is the answer.
Question 9 
A CPU has 24bit instructions. A program starts at address 300 (in decimal). Which one of the following is a legal program counter (all values in decimal)?
400  
500  
600  
700 
So finally we can say that the values in the program counter will always be the multiple of 3.
Hence, option (C) is correct.
Question 10 
In a binary max heap containing n numbers, the smallest element can be found in time
O(n)  
O(log n)  
O(log log n)  
O(1) 
We have to search all the elements to reach the smallest element and heap using linear search.
To traverse all elements using linear search will take O(n) time.
Question 11 
n1  
2n2  
n^{2} 
2) Weight of the minimum spanning tree = 22  1 + 23  2 + 24  3 + 25  4 .... + 2 n  (n1)  = 2n  2
Question 12 
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:
Queue  
Stack  
Heap  
BTree 
Question 13 
A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. The root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be.
log_{2}n  
n  
2n+1  
2^{n}1 
Note: Assume level numbers are start with 0.
Question 14 
Which one of the following in place sorting algorithms needs the minimum number of swaps?
Quick sort  
Insertion sort  
Selection sort  
Heap sort 
Question 15 
Consider the following Cprogram fragment in which i, j and n are integer variables.
for (i = n, j = 0; i >0; i /= 2, j += i);
Let val(j) denote the value stored in the variable j after termination of the for loop. Which one of the following is true?
val(j) = θ(logn)  
val(j) = θ(√n)  
val(j) = θ(n)  
val(j) = θ(n logn) 
Question 16 
Let S be an NPcomplete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomialtime reducible to R. Which one of the following statements is true?
R is NPcomplete  
R is NPhard  
Q is NPcomplete  
Q is NPhard 
Question 17 
An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array
Solves it in linear time using a left to right pass of the array  
Solves it in linear time using a right to left pass of the array  
Solves it using divide and conquer in time θ(nlogn)  
Solves it in time θ(n^{2}) 
Question 18 
We are given a set X = {x_{1}, .... x_{n}} where xi = 2^{i}. A sample S ⊆ X is drawn by selecting each x_{i} independently with probability p_{i} = 1/2. The expected value of the smallest number in sample S is:
1/n  
2  
√n  
n 
The given probability P_{i} is for selection of each item independently with probability 1/2.
Now, Probability for x_{1} to be smallest in S = 1/2
Now, Probability for x_{2} to be smallest in S = Probability of x_{1} not being in S × Probability of x_{2} being in S
= 1/2 × 1/2
Similarly, Probability x_{i} to be smallest = (1/2)^{i}
Now the Expected value is
Question 19 
Let L_{1} = {0^{n+m}1^{n}0^{m}n,m ≥ 0}, L_{2} = {0^{n+m}1^{n+m}0^{m}n,m ≥ 0}, and L_{3} = {0^{n+m}1^{n+m}0^{n+m}n,m ≥ 0}. Which of these languages are NOT context free?
L_{1} only  
L_{3} only  
L_{1} and L_{2}  
L_{2} and L_{3} 
But for L_{2} and L_{3} PDA implementation is not possible. The reason is, in L_{2} there are two comparison at a time, first the number of 0’s in beginning should be equal to 1’s and then 0’s after 1’s must be less than or equal to number of 1’s. Suppose for initial 0’s and 1’s are matched by using stack then after matching stack will become empty and then we cannot determine the later 0’s are equal to or less than number of 1’s. Hence PDA implementation is not possible. Similarly L_{3} also has the similar reason.
Question 20 
Consider the following log sequence of two transactions on a bank account, with initial balance 12000, that transfer 2000 to a mortgage payment and then apply a 5% interest.
1. T1 start 2. T1 B old=12000 new=10000 3. T1 M old=0 new=2000 4. T1 commit 5. T2 start 6. T2 B old=10000 new=10500 7. T2 commit
Suppose the database system crashes just before log record 7 is written. When the system is restarted, which one statement is true of the recovery procedure?
We must redo log record 6 to set B to 10500.
 
We must undo log record 6 to set B to 10000 and then redo log records 2 and 3.
 
We need not redo log records 2 and 3 because transaction T1 has committed.
 
We can apply redo and undo operations in arbitrary order because they are idempotent. 
So from above theory we can say that option (B) is the correct answer.
Question 21 
For each element in a set of size 2n, an unbiased coin is tossed. The 2n coin tosses are independent. An element is chosen if the corresponding coin toss were head. The probability that exactly n elements are chosen is:
No. of elements selected = n
Probability of getting head = ½
Probability of n heads out of 2n coin tosses is
2nC_{n}*(1/2)^{n}*(1/2)^{n} = 2nC_{n}/4^{n}
Question 22 
Let E, F and G be finite sets.
Let X = (E∩F)  (F∩G) and Y = (E  (E∩G))  (EF).
Which one of the following is true?
X ⊂ Y  
X ⊃ Y  
X = Y  
X  Y ≠ ∅ and Y  X ≠ ∅ 
E = {(1,1), (1,2), (1,3), (2,2), (2,3), (3,3), (3,1)}
F = {(1,1), (2,2), (3,3)}
G = {(1,3), (2,1), (2,3), (3,1)}
X = (E∩F)  (F∩G)
= {(1,1), (2,2), (3,3)  ∅}
= {(1,1), (2,2), (3,3)} (✔️)
Y = (E  (E∩G)  (E  F))
= (E  {(1,3), (2,3), (3,1)}  {(1,2), (1,3), (2,3), (3,1)})
= {(1,1), (1,2), (1,3), (2,2), (2,3), (3,3), (3,1)}  {(1,3), (2,2), (2,1)}  (1,2), (1,3), (2,3), (3,1)}
= {(1,1), (1,2), (2,2), (3,3)}  {(1,2), (1,3), (2,3), (3,1)}
= {(1,1), (2,2), (3,3)} (✔️)
X = Y
X = (E∩F)  (F∩G) = {2,5}  {5} = {2}
Y = (E  (E∩G)  (E  F))
= {(1,2,4,5)  (4,5)  (1,4)}
= {(1,2)  (1,4)}
= {2}
X = Y
Question 23 
F is an n×n real matrix. b is an n×1 real vector. Suppose there are two n×1 vectors, u and v such that, u≠v and Fu=b, Fv=b. Which one of the following statements is false?
Determinant of F is zero  
There are an infinite number of solutions to Fx=b  
There is an x≠0 such that Fx=0  
F must have two identical rows 
Fu = Fv
Fu  Fv = 0
F(u  v) = 0
Given u ≠ v
F = 0 (i.e., Singular matrix, so determinant is zero)
Option A is true.
⇾ Fx = b; where F is singular
It can have no solution (or) infinitely many solutions.
Option B is true.
⇾ x ≠ 0 such that Fx = 0 is True because F is singular matrix (“stated by singular matrix rules). Option C is true.
⇾ F can two identical columns and rows.
Option D is false.
Question 24 
Given a set of elements N = {1, 2, ..., n} and two arbitrary subsets A⊆N and B⊆N, how many of the n! permutations π from N to N satisfy min(π(A)) = min(π(B)), where min(S) is the smallest integer in the set of integers S, and π(S) is the set of integers obtained by applying permutation π to each element of S?
(nA ∪ B) A B  
(A^{2}+B^{2})n^{2}
 
n!(A∩B/A∪B)  
Two arbitrary subsets A⊆N and B⊆N.
Out of n! permutations π from N to N, to satisfy
min(π(A)) = min (π(B))
*) π(S) is the set of integers obtained by applying permutation π to each element of S.
If min(π(A)) =min (π(B)), say y = π(x) is the common minimum.
Since the permutation π is a 1to1 mapping of N,
x ∈ A∩B
∴ A∩B cannot be empty.
⇒ y = π(x)
= π(A∩B) is the minimum of π(A∪B) is the minimum of π(A) and π(B) are to be same.
You can think like
*) If the minimum of π(A) and π(B) are same [min π(A)] = min [π(B)]
then min(π(A∩B)) = min(π(A∪B))
∴ Total number is given by n! A∩B/A∪B
*) Finally
Considering all possible permutations, the fraction of them that meet this condition π(A∩B) / π(A∪B)
[The probability of single permutation].
Ex: N = {1, 2, 3, 4} A = {1, 3} B = {1, 2, 4}
Since π is one to one mapping
π(A∩B) = A∩B
∴ π(A) = {1, 2}
π(B) = {1, 4, 3}
π(A∩B) = {1}
π(A∪B) = {1, 2, 3, 4}
4! × 1/4 = 6
Question 25 
Let S = {1,2,3,....,m}, m > 3. Let x_{1}, x_{2},....x_{n} be the subsets of S each of size 3. Define a function f from S to the set of natural numbers as, f(i) is the number of sets of X_{j} that contain the element i. That is f(i) = {ji ∈ X_{j}}.
Then is
3m  
3n  
2m+1  
2n+1 
Question 26 
Which one of the first order predicate calculus statements given below correctly express the following English statement?
Tigers and lions attack if they are hungry or threatened.
∀x [(tiger(x) ∧ lion(x)) → {(hungry(x) ∨ threatened(x))
→ attacks(x)}]  
∀x [(tiger(x) ∨ lion(x)) → {(hungry(x) ∨ threatened(x))
∧ attacks(x)}]  
∀x [(tiger(x) ∨ lion(x)) → {(attacks(x) → (hungry (x)) ∨ threatened (x))}]  
∀x [(tiger(x) ∨ lion(x)) → {(hungry(x) ∨ threatened(x)) → attacks(x)}]

Here we have two cases.
i) If Tiger is hungry (or) threaten that will attack.
ii) If Lion is hungry (or) threaten that will attack.
If Tiger is hungry (or) threaten then both lion and tiger will not attack only Tiger will attack and viceversa.
Then answer is
∀x[(tiger(x) ∨ lion(x)) → {(hungry(x) ∨ threatened(x)) → attacks(x)}]
Note: Don’t confuse with the statement Tiger and Lion.
Question 27 
Consider the following propositional statements:
 P1 : ((A ∧ B) → C)) ≡ ((A → C) ∧ (B → C))
P2 : ((A ∨ B) → C)) ≡ ((A → C) ∨ (B → C))
Which one of the following is true?
P1 is a tautology, but not P2  
P2 is a tautology, but not P1  
P1 and P2 are both tautologies  
Both P1 and P2 are not tautologies 
Both P1 and P2 are not Tautologies.
Question 28 
A logical binary relation ⊙,is defined as follows:
Let ~ be the unary negation (NOT) operator, with higher precedence than ⊙. Which one of the following is equivalent to A∧B ?
(~A⊙B)  
~(A⊙~B)  
~(~A⊙~B)  
~(~A⊙B) 
Question 29 
If s is a string over (0 + 1)* then let n_{0}(s) denote the number of 0’s in s and n_{1}(s) the number of 1’s in s. Which one of the following languages is not regular?
L = {s ∈ (0+1)*  n_{0}(s) is a 3digit prime}  
L = {s ∈ (0+1)*  for every prefix s' of s,n_{0}(s')  n_{1}(s') ≤ 2}  
L = {s ∈ (0+1)* n_{0}(s)  n_{1}(s) ≤ 4}
 
L = {s ∈ (0+1)*  n_{0}(s) mod 7 = n_{1}(s) mod 5 = 0}

Option B: The DFA contains 6 states
State 1: n_{0}(s')  n_{1}(s') = 0
State 2: n_{0}(s')  n_{1}(s') = 1
State 3: n_{0}(s')  n_{1}(s') = 2
State 4: n_{0}(s')  n_{1}(s') = 1
State 5: n_{0}(s')  n_{1}(s') = 2
State 6: Dead state (trap state)
Hence it is regular.
Option D: Product automata concept is used to construct the DFA.
mod 7 has remainders {0,1,2,3,4,5,6} and mod 5 remainders {0,1,2,3,4}
So product automata will have 35 states.
But option C has infinite comparisons between number of 0’s and 1’s.
For ex: n_{0}(s) = 5 and n_{1}(s) = 1 then n_{0}(s)  n_{1}(s) = 4 and if n_{0}(s) = 15 and n_{1}(s) = 11 then n_{0}(s)  n_{1}(s) = 4.
Hence this is CFL.
Question 30 
For S ∈ (0+1) * let d(s) denote the decimal value of s (e.g. d(101) = 5). Let L = {s ∈ (0+1)*d(s)mod5 = 2 and d(s)mod7 = 4}.
Which one of the following statements is true?
L is recursively enumerable, but not recursive  
L is recursive, but not contextfree  
L is contextfree, but not regular  
L is regular 
L_{2} = {s ∈ (0 + 1)*  d(s) mod7 = 4}, we can construct the DFA for this which will have 7 states (remainders 0,1,2,3,4,5,6)
Since L_{1} and L_{2} have DFAs, hence they are regular. So the resulting Language.
L = L_{1} ∩ L_{2} (compliment) must be regular (by closure properties, INTERSECTION of two regular languages is a regular language).
Question 31 
Let SHAM_{3} be the problem of finding a Hamiltonian cycle in a graph G = (V,E) with V divisible by 3 and DHAM_{3} be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?
Both DHAM_{3} and SHAM_{3} are NPhard  
SHAM_{3} is NPhard, but DHAM_{3} is not  
DHAM_{3} is NPhard, but SHAM_{3} is not  
Neither DHAM_{3} nor SHAM_{3} is NPhard 
Question 32 
Consider the following statements about the context free grammar
G = {S → SS, S → ab, S → ba, S → ε}
 I. G is ambiguous
II. G produces all strings with equal number of a’s and b’s
III. G can be accepted by a deterministic PDA.
Which combination below expresses all the true statements about G?
I only  
I and III only  
II and III only  
I, II and III 
G doesn’t product all strings of equal number of a’s and b’s, for ex: string “aabb” doesn’t generate by grammar G.
The language generated by G can be accepted by DPDA. We can notice that grammar G generates, a’s and b’s in pair, i.e. either “ab” or “ba”, so the strings in language are {ab, ba, abab, abba, baba, ….}
We can design the DPDA:
Question 33 
Let L_{1} be a regular language, L_{2} be a deterministic contextfree language and L_{3} a recursively enumerable, but not recursive, language. Which one of the following statements is false?
L_{1} ∩ L_{2} is a deterministic CFL  
L_{3} ∩ L_{1} is recursive  
L_{1} ∪ L_{2} is context free  
L_{1} ∩ L_{2} ∩ L_{3} is recursively enumerable 
L ∩ R = L ( i.e. L Intersection R is same type as L )
So L_{1} ∩ L_{2} is a deterministic CFL.
Option B is false, as L_{3} is recursive enumerable but not recursive, so intersection with L_{1} must be recursive enumerable, but may or may not be recursive.
Option C is true, as by closure property (R is a regular language and L is any language)
L U R = L ( i.e. L UNION R is same type as L )
So, L_{1} ∪ L_{2} is deterministic context free, hence it is also context free.
Option D is true, as L_{1} ∩ L_{2} is DCFL and DCFL ∩ L_{3} is equivalent to DCFL ∩ Recursive enumerable.
As every DCFL is recursive enumerable, so it is equivalent to Recursive enumerable ∩ Recursive enumerable. And recursive enumerable are closed under INTERSECTION so it will be recursive enumerable.
Question 34 
Consider the regular language L = (111 + 11111)*. The minimum number of states in any DFA accepting this languages is:
3  
5  
8  
9 
i.e. it generates any string which can be obtained by repetition of three and five 1’s (means length 3, 6, 8, 9, 10, 11, …}
The DFA for the L = (111 + 11111)* is given below.
Question 35 
Consider the circuit above. Which one of the following options correctly represents f(x,y,z)?
= xy + zy’ + y’z’x
= x(y+y’z’) + zy’
= x(y+z’) + y’z
= xy + xz’ + y’z
Question 36 
Given two three bit numbers a_{2}a_{1}a_{0} and b_{2}b_{1}b_{0} and c, the carry in, the function that represents the carry generate function when these two numbers are added is:
Carry c_{1} = a_{0}b_{0}
Carry c_{2} = a_{2}b_{2} + c_{1}(a_{2} ⊕ b_{2} )
= a_{1}b_{1} +c_{1} (a_{1} b’_{1}+ a’_{1} b_{1} )
= a_{1}b_{1} +c_{1} a_{1} b’_{1}+ c_{1} a’_{1} b_{1}
= (a_{1}b_{1} + c_{1}a_{1} b’_{1})+ (c_{1} a’_{1} b_{1} + a_{1}b_{1} )
= a_{1}(b_{1}+c_{1}) +b_{1} (c_{1} + a_{1})
= a_{1}b_{1}+b_{1}c_{1}+a_{1}c_{1}
Carry c_{3} = a_{2}b_{2} + c_{2}(a_{2} ⊕ b_{2})
= a_{2}b_{2} + c_{2}(a’_{2}b_{2} + a_{2}b’_{2} )
= a_{2}b_{2} + b_{2}c_{2} + a_{2}c_{2}
= a_{2}b_{2}+a_{2}a_{1}b_{1}+a_{2}a_{1}a_{0}b_{0}+a_{2}a_{0}b_{1}b_{0}+a_{1}b_{2}b_{1}+a_{1}a_{0}b_{2}b_{0}+a_{0}b_{2}b_{1}b_{0}
Question 37 
Consider the circuit in the diagram. The ⊕ operator represents ExOR. The D flipflops are initialized to zeroes (cleared).
The following data: 100110000 is supplied to the “data” terminal in nine clock cycles. After that the values of q2q1q0 are:
000  
001  
010  
101 
Question 38 
Consider a Boolean function f(w,x,y,z). Suppose that exactly one of its inputs is allowed to change at a time. If the function happens to be true for two input vectors i_{1} = 〈w_{1}, x_{1}, y_{1}, z_{1}〉 and i_{2} = 〈w_{2}, x_{2}, y_{2}, z_{2}〉, we would like the function to remain true as the input changes from vectors i_{1} to i_{2} (i_{1} and i_{2} differ in exactly one bit position), without becoming false momentarily. Let f(w,x,y,z) = ∑(5,7,11,12,13,15). Which of the following cube covers of f will ensure that the required property is satisfied?
f = X_{1} * X_{2} + X_{1}' * X_{3}
If (X_{1}, X_{2}, X_{3}) = (1,1,1) then f=1 because X_{1} * X_{2} =1 X_{1}' * X_{3} = 0.
Let the input is changed from 111 to 011 , then f = 1 because X_{1} * X_{2} = 0 X_{1}' * X_{3} =1.
The output f will be momentarily 0 if AND gate X_{1} * X_{2} is faster than the AND gate X_{1}' * X_{}3.
This Hazard can be avoided by adding the term X_{2} * X_{3} (because X_{1} is in true form in first term and in complement form in the second term . So pick the fixed terms X_{2} and X_{3} from both terms) to f i.e f = X_{1} * X_{2} + X_{1}' * X_{3} + X_{2} * X_{3}
Option D is equivalent to f(w, x, y, z) = ∑(5,7,11,12,13,15)
Question 39 
We consider the addition of two 2’s complement numbers b_{n1}b_{n2}...b_{0} and a_{n1}a_{n2}…a_{0}. A binary adder for adding unsigned binary numbers is used to add the two numbers. The sum is denoted by c_{n1}c_{n2}c_{0} and the carryout by c_{out}. Which one of the following options correctly identifies the overflow condition?
1. The sign bits are same i.e MSB bits are same.
2. Carry_in ≠ Carry_out.
In option B, the MSB are equal.
Question 40 
Consider numbers represented in 4bit gray code. Let h_{3}h_{2}h_{1}h_{0} be the gray code representation of a number n and let g_{3}g_{2}g_{1}g_{0} be the gray code of (n+1)(modulo 16) value of the number. Which one of the following functions is correct?
g_{0}(h_{3}h_{2}h_{1}h_{0}) = Σ(1,2,3,6,10,13,14,15)  
g_{1}(h_{3}h_{2}h_{1}h_{0}) = Σ(4,9,10,11,12,13,14,15)  
g_{2}(h_{3}h_{2}h_{1}h_{0}) = Σ(2,4,5,6,7,12,13,15)  
g_{3}(h_{3}h_{2}h_{1}h_{0}) = Σ(0,1,6,7,10,11,12,13)

g_{2}(h_{3}h_{2}h_{1}h_{0}) = Σ(2,4,5,6,7,12,13,15)
Question 41 
A CPU has a cache with block size 64 bytes. The main memory has k banks, each bank being c bytes wide. Consecutive c − byte chunks are mapped on consecutive banks with wraparound. All the k banks can be accessed in parallel, but two accesses to the same bank must be serialized. A cache block access may involve multiple iterations of parallel bank accesses depending on the amount of data obtained by accessing all the k banks in parallel. Each iteration requires decoding the bank numbers to be accessed in parallel and this takes. k/2 ns The latency of one bank access is 80 ns. If c = 2 and k = 24, the latency of retrieving a cache block starting at address zero from main memory is:
92 ns  
104 ns  
172 ns  
184 ns 
Latency = 80 ns
k = 24
No. of banks are accessed in parallel , then it takes k/2 ns = 24/2 = 12ns
Decoding time = 12ns
Size of each bank C = 2 bytes
Each Bank memory is 2 bytes, and there is 24 banks are there, in one iteration they may get 2*24 = 48 bytes
And getting 64 bytes requires 2 iteration.
T = decoding time + latency = 12+80 = 92
For 2 iterations = 92×2 = 184ns
Question 42 
A CPU has a fivestage pipeline and runs at 1 GHz frequency. Instruction fetch happens in the first stage of the pipeline. A conditional branch instruction computes the target address and evaluates the condition in the third stage of the pipeline. The processor stops fetching new instructions following a conditional branch until the branch outcome is known. A program executes 10^{9} instructions out of which 20% are conditional branches. If each instruction takes one cycle to complete on average, the total execution time of the program is:
1.0 second  
1.2 seconds  
1.4 seconds  
1.6 seconds 
20% are condition branches out of 10^{9}
⇒ 20/100 × 10^{9}
⇒ 2 × 10^{8}
In third stage of pipeline it consists of 2 stage cycles.
Total cycle penalty = 2 × 2 × 10^{8} = 4 × 10^{8}
Clock speed = 1 GHz
Each Instruction takes 1 cycle i.e., 10^{9} instructions.
Total execution time of a program is
= (10^{9} / 10^{9}) +((4× 10^{8}) / 10^{9}) = 1+0.4 = 1.4 seconds
Question 43 
Consider a new instruction named branchonbitset (mnemonic bbs). The instruction “bbs reg, pos, label” jumps to label if bit in position pos of register operand reg is one. A register is 32 bits wide and the bits are numbered 0 to 31, bit in position 0 being the least significant. Consider the following emulation of this instruction on a processor that does not have bbs implemented.
temp ← reg & mask Branch to label if temp is nonzero.
The variable temp is a temporary register. For correct emulation, the variable mask must be generated by:
mask ← 0×1 << pos  
mask ← 0×ffffffff >> pos  
mask ← pos  
mask ← 0×f 
So for mask to have 1 only in position pos and 0s in all the other positions, we can get it by doing left shift on 1, pos number of times.
Out of the given options, in option A this left shift operation on 1 is performed pos number of times. Hence option A is the answer.
Question 44 
Station A uses 32 byte packets to transmit messages to Station B using a sliding window protocol. The round trip delay between A and B is 80 milliseconds and the bottleneck bandwidth on the path between A and B is 128 kbps. What is the optimal window size that A should use?
20  
40  
160  
320 
Round trip delay = 2 * T_{p} = 80 ms (given)
Optimal window size is = (T_{t} + 2*T_{p}) / T_{t} = 82 / 2 = 41
Option is not given, closest option is 40.
Question 45 
Two computers C1 and C2 are configured as follows. C1 has IP address 203.197.2.53 and netmask 255.255.128.0. C2 has IP address 203.197.75.201 and netmask 255.255.192.0. Which one of the following statements is true?
C1 and C2 both assume they are on the same network  
C2 assumes C1 is on same network, but C1 assumes C2 is on a different network  
C1 assumes C2 is on same network, but C2 assumes C1 is on a different network  
C1 and C2 both assume they are on different networks 
Subnet mask for C1 is 255.255.128.0.
So it finds the Network ID as,
C1 → 203.197.2.53 AND 255.255.128.0 = 203.197.0.0
C2 → 203.197.75.201 AND 255.255.128.0 = 203.197.0.0
Both same.
From C2 side,
Subnet mask for C2 is 255.255.192.0.
So it finds the network ID as,
C1 → 203.197.2.53 AND 255.255.192.0 = 203.197.0.0
C2 → 203.197.75.201 AND 255.255.192.0 = 203.197.64.0
Both different.
Hence, option 'C' is correct.
Question 46 
Station A needs to send a message consisting of 9 packets to Station B using a sliding window (window size 3) and gobackn error control strategy. All packets are ready and immediately available for transmission. If every 5^{th} packet that A transmits gets lost (but no acks from B ever get lost), then what is the number of packets that A will transmit for sending the message to B?
12  
14  
16  
18 
Frame sequence for 9 frame is shown below. Frame with bold sequence number gets lost.
1 2 3 4 [5 6 7] 5 6 [7 8 9] 7 8 9 9 = 16
Question 47 
Consider the following graph:
Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm?
(a—b),(d—f),(b—f),(d—c),(d—e)  
(a—b),(d—f),(d—c),(b—f),(d—e)  
(d—f),(a—b),(d—c),(b—f),(d—e)  
(d—f),(a—b),(b—f),(d—e),(d—c) 
1. It follows like forest structure (Means we are disconnecting all the edges connected to vertices).
2. Sort edge weights in Ascending order.
3. Always select the minimum edge weight first according to Spanning Tree rules.
Note: The edge de cannot be considered before dc.
Question 48 
Let T be a depth first search tree in an undirected graph G. Vertices u and n are leaves of this tree T. The degrees of both u and v in G are at least 2. Which one of the following statements is true?
There must exist a vertex w adjacent to both u and v in G  
There must exist a vertex w whose removal disconnects u and v in G  
There must exist a cycle in G containing u and v
 
There must exist a cycle in G containing u and all its neighbours in G 
Question 49 
An implementation of a queue Q, using two stacks S1 and S2, is given below:
void insert(Q, x) { push (S1, x); } void delete(Q){ if(stackempty(S2)) then if(stackempty(S1)) then { print(“Q is empty”); return; } else while (!(stackempty(S1))){ x=pop(S1); push(S2,x); } x=pop(S2); }
Let n insert and m(<=n) delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?
n+m ≤ x < 2n and 2m ≤ y ≤ n+m  
n+m ≤ x< 2n and 2m ≤y ≤ 2n  
2m ≤ x< 2n and 2m ≤ y ≤ n+m  
2m ≤ x < 2n and 2m ≤ y ≤ 2n 
Best case:
First push m elements in S1 then pop m elements from S1 and push them in S2 and then pop all m elements from S2. Now push remaining (nm) elements to S1.
So total push operation
= m + m + (nm)
= n+m
Worst Case:
First push all n elements in S1. Then pop n elements from S1 and push them into S2. Now pop m elements from S2.
So total push operation
= n+n
= 2n
Now lets consider for pop operation, i.e., y.
For best case:
First push m elements in S1, then pop m elements and push them in S2. Now pop that m elements from S2. Now push remaining (nm) elements in S1.
So total pop operation
= m+m
= 2m
For worst case:
First push n elements in S1, then pop them from S1 and push them into S2. Now pop m elements fro m S2.
So total pop operation
= n+m
Therefore, option A is correct answer.
Question 50 
A set X can be represented by an array x[n] as follows:
Consider the following algorithm in which x,y and z are Boolean arrays of size n:
algorithm zzz(x[] , y[], z []) { int i; for (i=O; i<n; ++i) z[i] = (x[i] ^ ~y[i]) V (~x[i] ^ y[i]) }
The set Z computed by the algorithm is:
(X ∪ Y)  
(X ∩ Y)  
(XY) ∩ (YX)  
(XY) ∪ (YX) 
~X[i] ∧ Y[i] can be written as Y  X.
'∨' can be written as Union.
∴ (XY) Union (YX)
Question 51 
Consider the following recurrence:
Which one of the following is true?
T(n) = θ(log logn)
 
T(n) = θ(logn)  
T(n) = θ(√n)  
T(n) = θ(n) 
Let n =2^{m}
T(2^{m}) = 2T(2^{m/2}) + 1 (1)
Let T(2^{m}) = S(m)
Then equation (1) becomes,
S(m) = 2S(m/2) + 1
So now lets apply Master's theorem,
a=2, b=2, k=0
Since, a>b^{k}, so Case 1 applied here
But m = log n
So finally the answer is,
O(log n)
Question 52 
The median of n elements can be found in O(n) time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?
θ(n)  
θ(n logn)  
θ(n^{2})  
θ(n^{3}) 
T(n) = 2T(n/2) +O(n)
The above recurrence in the form of masters theorem: a=2, b=2, k=1, p=0. Since, a=b^{k}, so Case2 is applied
and also p > 1, so
Question 53 
Consider the following Cfunction in which a[n] and b[m] are two sorted integer arrays and c[n + m] be another integer array.
void xyz(int a[], int b [], int c[]) { int i, j, k; i = j = k = O; while ((i < n) && (j < m)) if (a[i] < b[j]) c[k++] = a[i++]; else c[k++] = b[j++]; }
Which of the following condition(s) hold(s) after the termination of the while loop?
(i) j < m, k = n+j1, and a[n1] < b[j] if i = n (ii) i < n, k = m+i1, and b[m1] ≤ a[i] if j = m
only (i)  
only (ii)  
either (i) or (ii) but not both  
neither (i) nor (ii) 
Suppose i=n. This would mean all elements from array 'a' are added to 'c' and k must be incremented by n. 'c' would also contain j elements from array 'b'.
So, number of elements in 'c' would be n+j and hence k=n+j.
Similarly, when j=m, k=m+i.
Hence, option (D) is correct.
Question 54 
Given two arrays of numbers a_{1}, a_{2}, a_{3},...a_{n} and b_{1}, b_{2}, .. b_{n} where each number is 0 or 1, the fastest algorithm to find the largest span(i, j) such that a_{i} + a_{i+1}, ....a_{j} = b_{i} + b_{i+1}, ... b_{j}. or report that there is not such span,
Takes O(3^{n}) and Ω(2^{n}) time if hashing is permitted  
Takes O(n^{3}) and Ω(n^{2.5}) time in the key comparison model  
Takes θ(n) time and space  
Takes O(√n) time only if the sum of the 2n elements is an even number 
1. Since there are total n elements, maximum sum is n for both arrays.
2. Difference between two sums varies from n to n. So there are total 2n + 1 possible values of difference.
3. If differences between prefix sums of two arrays become same at two points, then subarrays between these two points have same sum.
Question 55 
Consider these two functions and two statements S1 and S2 about them
int work1(int *a, int i, int j) int work2(int *a, int i, int j) { { int x = a[i+2]; int t1 = i+2; a[j] = x+1; int t2 = a[t1]; return a[i+2] – 3; a[j] = t2+1; } return t2 – 3; }
 S1: The transformation form work1 to work2 is valid, i.e., for any program state and input arguments, work2 will compute the same output and have the same effect on program state as work1
S2: All the transformations applied to work1 to get work2 will always improve the performance (i.e reduce CPU time) of work2 compared to work1
S1 is false and S2 is false
 
S1 is false and S2 is true  
S1 is true and S2 is false  
S1 is true and S2 is true 
So, given statement is wrong.
S1: Let us assume an array = {1,2,3,4,5} and i=0.
Let j = i+2 = 0+2 = 2
For the respective example work1 and work2 results 1 and 0, so S1 statement is False.
Question 56 
Consider the following code written in a passbyreference language like FORTRAN and these statements about the code.
subroutine swap(ix,iy) it = ix L1 : ix = iy L2 : iy = it end ia = 3 ib = 8 call swap (ia, 1b+5) print *, ia, ib end
S1: The compiler will generate code to allocate a temporary nameless cell, initialize it to 13, and pass the address of the cell swap S2: On execution the code will generate a runtime error on line L1 S3: On execution the code will generate a runtime error on line L2 S4: The program will print 13 and 8 S5: The program will print 13 and 2
Exactly the following set of statement(s) is correct:
S1 and S2  
S1 and S4  
S3  
S1 and S5 
Swap (8, 13)
⇒ ia will returns value with 13.
⇒ ib is unchanged, because here we using pass by reference value.
➝ Temporary nameless is initialized to 13.
➝ There is No runtime error.
Question 57 
Consider this C code to swap two integers and these five statements after it:
void swap(int *px, int *py) { *px = *px  *py; *py = *px + *py; *px = *py  *px; }
S1: will generate a compilation error S2: may generate a segmentation fault at runtime depending on the arguments passed S3: correctly implements the swap procedure for all input pointers referring to integers stored in memory locations accessible to the process S4: implements the swap procedure correctly for some but not all valid input pointers S5: may add or subtract integers and pointers.
S1  
S2 and S3  
S2 and S4  
S2 and S5 
We may get the segmentation fault if the pointer values are constant (i.e., px or py) (or) (px or py) are points to a memory location is invalid.
S4:
Swap procedure can be implemented correctly but not for all input pointers because arithmetic overflow may occur based on input values.
Question 58 
Consider the following grammar:
S → FR R → S  ε F → id
In the predictive parser table, M, of the grammar the entries M[S,id] and M[R,$] respectively.
{S → FR} and {R → ε}
 
{S → FR} and { }  
{S → FR} and {R → *S}  
{F → id} and {R → ε} 
The representation M[X,Y] means X represents Variable (rows) and Y represents terminals (columns).
The productions are filled in parsing table by the below mentioned rules:
For every production P → α, we have:
Rule 1: If P → α is a production then add this production for each terminal “t” which is in FIRST of [α] i.e., ADD P → α to M[P, a]
Rule 2: If “ϵ” belongs to FIRST of [P] then add P → α to M[P, b] where “b” represents terminals FOLLOW[P].
By the above rules, we can see that production S → FR will go M[S, a] where “a” is FIRST [FR] which is equal to FIRST[F] = id, So S → FR will go in M[S,id].
Since in the production R→ϵ , FIRST[ϵ] = ϵ, hence the production will go in M[R, b] where “b” represents terminals FOLLOW[R] and FOLLOW[R] = $, so production R→ϵ will go in M[R,$]
Question 59 
Consider the following translation scheme.
S → ER R → *E{print("*");}Rε E → F + E {print("+");}F F → (S)id {print(id.value);}
Here id is a token that represents an integer and id.value represents the corresponding integer value. For an input '2 * 3 + 4', this translation scheme prints
2 * 3 + 4  
2 * +3 4
 
2 3 * 4 +  
2 3 4+* 
Now perform post order evaluation, you will get output as,
2 3 4 + *
Question 60 
Consider the following C code segment.
for (i = 0, i < n; i++) { for (j = 0; j < n; j++) { if (i%2) { x += (4*j + 5*i); y += (7 + 4*j); } } }
Which one of the following is false?
The code contains loop invariant computation  
There is scope of common subexpression elimination in this code  
There is scope of strength reduction in this code  
There is scope of dead code elimination in this code

→ 5*i can be moved out of inner loop. So can be i%2, here loop invariant computation can be done, so option A is correct.
→ 4*i, 5*j can also be replaced so there is a scope of strength reduction. So C is true.
→ But there is no dead code to eliminate, we can replace the variable representation only.
Question 61 
The atomic fetchandset x, y instruction unconditionally sets the memory location x to 1 and fetches the old value of x n y without allowing any intervening access to the memory location x. consider the following implementation of P and V functions on a binary semaphore S.
void P (binary_semaphore *s) { unsigned y; unsigned *x = &(s>value); do { fetchandset x, y; } while (y); } void V (binary_semaphore *s) { S>value = 0; }
Which one of the following is true?
The implementation may not work if context switching is disabled in P  
Instead of using fetchandset, a pair of normal load/store can be used  
The implementation of V is wrong  
The implementation of V is wrong 
B) If we use normal load and store instead of Fetch and Set, then there can be chance that more than one process sees S.value as 0 and then mutual exclusion will not be satisfied. So wrong.
C) Here we are setting S→value to 0, which is correct. This option that's why wrong.
D) Only one process can be in critical section at any time. So this option is wrong.
Question 62 
A CPU generates 32bit virtual addresses. The page size is 4 KB. The processor has a translation lookaside buffer (TLB) which can hold a total of 128 page table entries and is 4way set associative. The minimum size of the TLB tag is:
11 bits  
13 bits  
15 bits  
20 bits 
Virtual Address = 32 bit
No. of bits needed to address the page frame = 32  12 = 20
TLB can hold 128 page table entries with 4way set associative
⇒ 128/4=32=2^{5}
→ 5 bits are needed to address a set.
→ The size of TLB tag = 20  5 = 15 bits
Question 63 
A computer system supports 32bit virtual addresses as well as 32bit physical addresses. Since the virtual address space is of the same size as the physical address space, the operating system designers decide to get rid of the virtual memory entirely. Which one of the following is true?
Efficient implementation of multiuser support is no longer possible
 
The processor cache organization can be made more efficient now
 
Hardware support for memory management is no longer needed  
CPU scheduling can be made more efficient now 
→ Because special hardware support needed only for virtual memory.
Question 64 
Consider three processes (process id 0, 1, 2 respectively) with compute time bursts 2, 4 and 8 time units. All processes arrive at time zero. Consider the longest remaining time first (LRTF) scheduling algorithm. In LRTF ties are broken by giving priority to the process with the lowest process id. The average turnaround time is:
13 units  
14 units  
15 units  
16 units

Avg TAT = 12+13+14/3 = 39/3 = 13 units
Question 65 
Consider three processes, all arriving at time zero, with total execution time of 10, 20 and 30 units, respectively. Each process spends the first 20% of execution time doing I/O, the next 70% of time doing computation, and the last 10% of time doing I/O again. The operating system uses a shortest remaining compute time first scheduling algorithm and schedules a new process either when the running process gets blocked on I/O or when the running process finishes its compute burst. Assume that all I/O operations can be overlapped as much as possible. For what percentage of time does the CPU remain idle?
0%  
10.6%  
30.0%  
89.4% 
Total time needed to complete the execution = 47
Idle time = 2+3 = 5
Percentage of Idle time = 5/47 × 100 =10.6%
Question 66 
Consider the following snapshot of a system running n processes. Process i is holding x_{i} instances of a resource R, 1≤i≤n. Currently, all instances of R are occupied. Further, for all i, process i has placed a request for an additional y_{i} instances while holding the x_{i} instances it already has. There are exactly two processes p and q such that y_{p} = y_{q} = 0. Which one of the following can serve as a necessary condition to guarantee that the system is not approaching a deadlock?
min (x_{p}, x_{q}) < max_{k≠p,q}y_{k}  
x_{p} + x_{q} ≥ min_{k≠p,q}y_{k}  
max (x_{p}, x_{q}) > 1  
min (x_{p}, x_{q}) > 1 
→ When two (or) more processes waiting for another process to release the resources.
→ P and Q can execute if they have sufficient resources, they don’t wait for extra resources (i.e., X_{p}+ X_{q}) required.
→ Option B can satisfies the corresponding equation i.e., X_{p}+ X_{q} >= min(Y_{k}) where k != p and k != q.
Here we have sufficient resources.
Question 67 
Consider the relation account (customer, balance) where customer is a primary key and there are no null values. We would like to rank customers according to decreasing balance. The customer with the largest balance gets rank 1. ties are not broke but ranks are skipped: if exactly two customers have the largest balance they each get rank 1 and rank 2 is not assigned.
Query1: select A.customer, count(B.customer) from account A, account B where A.balance <=B.balance group by A.customer Query2: select A.customer, 1+count(B.customer) from account A, account B where A.balance < B.balance group by A.customer
Consider these statements about Query1 and Query2.
1. Query1 will produce the same row set as Query2 for some but not all databases. 2. Both Query1 and Query2 are correct implementation of the specification 3. Query1 is a correct implementation of the specification but Query2 is not 4. Neither Query1 nor Query2 is a correct implementation of the specification 5. Assigning rank with a pure relational query takes less time than scanning in decreasing balance order assigning ranks using ODBC.
Which two of the above statements are correct?
2 and 5  
1 and 3  
1 and 4  
3 and 5 
The customer with largest balance gets rank 1. Ties are broken with ranks are skipped.
So, both queries may doesn’t give same output. Statement 4 is correct.
Question 68 
Consider the relation "enrolled(student, course)" in which (student, course) is the primary key, and the relation "paid(student, amount)" where student is the primary key. Assume no null values and no foreign keys or integrity constraints. Given the following four queries:
Query1: select student from enrolled where student in (select student from paid) Query2: select student from paid where student in (select student from enrolled) Query3: select E.student from enrolled E, paid P where E.student = P.student Query4: select student from paid where exists (select * from enrolled where enrolled.student = paid.student)
Which one of the following statements is correct?
All queries return identical row sets for any database.
 
Query2 and Query4 return identical row sets for all databases but there exist databases for which Query1 and Query2 return different row sets.
 
There exist databases for which Query3 returns strictly fewer rows than Query2.  
There exist databases for which Query4 will encounter an integrity violation at runtime.

Query1 : Output
abcd
abcd
PQRS
Query 2 : Output
abcd
PQRS
Query 3 : Output
abcd
PQRS
Query 4 : Output
abcd
PQRS
Query 2 & Query 4 gives same results but Query 1 & Query 3 gives different results.
Question 69 
Consider the relation enrolled(student, course) in which (student, course) is the primary key, and the relation paid(student, amount), where student is the primary key. Assume no null values and no foreign keys or integrity constraints. Assume that amounts 6000, 7000, 8000, 9000 and 10000 were each paid by 20% of the students. Consider these query plans (Plan 1 on left, Plan 2 on right) to "list all courses taken by students who have paid more than x".
A disk seek takes 4ms, disk data transfer bandwidth is 300 MB/s and checking a tuple to see if amount is greater than x takes 10 microseconds. Which of the following statements is correct?
Plan 1 and Plan 2 will not output identical row sets for all databases.
 
A course may be listed more than once in the output of Plan 1 for some databases.  
For x = 5000, Plan 1 executes faster than Plan 2 for all databases.
 
For x = 9000, Plan I executes slower than Plan 2 for all databases.

While analyze the plan1 and plan2 does lesser number of comparisons compared to plan1.
i) The join table consists of two tables will have more rows. So comparisons are needed to find amount greater than x.
ii) Join operation consists of more number of comparisons as the second table will have more rows in plan2 compared to plan1.
Question 70 
The following functional dependencies are given:
AB → CD, AF → D, DE → F, C → G, F → E, G → A.
Which one of the following options is false?
{CF}^{+} = {ACDEFG}  
{BG}^{+} = {ABCDG}
 
{AF}^{+} = {ACDEFG}  
{AB}^{+} = {ABCDFG} 
AF → D
DE → F
C → G
F → E
G → A
CF^{+} = {G,E,A,D,C,F} = {A,C,D,E,F,G} (✔️)
BG^{+} = {B,G,A,C,D} = {A,B,C,D,G} (✔️)
AF^{+} = {D,E,A,F} = {A,D,E,F} (❌)
AB^{+} = {A,B,C,D,G} (❌)
Question 71 
The 2^{n} vertices of a graph G corresponds to all subsets of a set of size n, for n ≥ 6. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.
The number of vertices of degree zero in G is:
1  
n  
n+1  
2^{n} 
= no. of subsets with size less than or equal to 1
= n+1, because in question it is given that the two vertices are connected if and only if the corresponding sets intersect in exactly two elements.
Question 72 
The 2^{n} vertices of a graph G corresponds to all subsets of a set of size n, for n ≥ 6. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.
The maximum degree of a vertex in G is:
2^{n2}  
2^{n3} × 3  
2^{n1} 
(k(_{c}))_{2} 2^{nk}
∴ We need to find 'k' value such that, the value will be maximum.[k should be an integer].
If you differentiate (k(_{c}))_{2} 2^{nk} w.r.t. k and equal to 0.
You will get k = 2/(log_{e})2 which is not an integer.
So you can see it like
∴ The maximum degree 3⋅2^{n3} at k=3 or k=4.
Question 73 
The 2^{n} vertices of a graph G corresponds to all subsets of a set of size n, for n ≥ 6. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.
The number of connected components in G is:
n  
n+2  
2^{n/2}  
2^{n} / n 
While other nodes are connected so that total number of connected components is (n+1)+1
(here we are adding 1 because it is connected corresponding remaining vertices)
= n+2
Question 74 
Consider two cache organizations: The first one is 32 KB 2way set associative with 32byte block size. The second one is of the same size but direct mapped. The size of an address is 32 bits in both cases. A 2to1 multiplexer has a latency of 0.6 ns while a kbit comparator has a latency of k/10 ns. The hit latency of the set associative organization is h_{1} while that of the direct mapped one is h_{2}.
The value of h_{1} is:
2.4 ns  
2.3 ns  
1.8 ns  
1.7 ns 
Block size = 32 bytes
No. of blocks = 2 (2way set associative)
No. of combinations = Cache size / (Block size×No. of blocks) = (32×2^{10}B) / (32×2) = 29
Index bits = 9
No. of set bits = 5 (∵ cache block size is 32 bytes = 2^{5} bytes)
No. of Tag bits = 32  9  5 = 18
Hit latency = Multiplexer latency + latency
= 0.6 + (18/10)
= 0.6 + 1.8
= 2.4 ns
Question 75 
Consider two cache organizations: The first one is 32 KB 2way set associative with 32byte block size. The second one is of the same size but direct mapped. The size of an address is 32 bits in both cases. A 2to1 multiplexer has a latency of 0.6 ns while a kbit comparator has a latency of k/10 ns. The hit latency of the set associative organization is h_{1} while that of the direct mapped one is h_{2}.
The value of h_{2} is:
2.4 ns  
2.3 ns  
1.8 ns  
1.7 ns 
For k,
∴ Hit latency = 17/1 = 1.7 ns
Question 76 
A 3ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property.
Which one of the following is a valid sequence of elements in an array representing 3ary max heap?
1, 3, 5, 6, 8, 9
 
9, 6, 3, 1, 8, 5  
9, 3, 6, 8, 5, 1  
9, 5, 6, 8, 3, 1 
Question 77 
A 3ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property.
Suppose the elements 7, 2, 10 and 4 are inserted, in that order, into the valid 3ary max heap found in the above question, Q.76. Which one of the following is the sequence of items in the array representing the resultant heap?
10, 7, 9, 8, 3, 1, 5, 2, 6, 4  
10, 9, 8, 7, 6, 5, 4, 3, 2, 1  
10, 9, 4, 5, 7, 6, 8, 2, 1, 3  
10, 8, 6, 9, 7, 2, 3, 4, 1, 5 
Question 78 
Barrier is a synchronization construct where a set of processes synchronizes globally i.e. each process in the set arrives at the barrier and waits for all others to arrive and then all processes leave the barrier. Let the number of processes in the set be three and S be a binary semaphore with the usual P and V functions. Consider the following C implementation of a barrier with line numbers shown on left.
void barrier (void) { 1: P(S); 2: process_arrived++; 3. V(S); 4: while (process_arrived !=3); 5: P(S); 6: process_left++; 7: if (process_left==3) { 8: process_arrived = 0; 9: process_left = 0; 10: } 11: V(S); }
The variables process_arrived and process_left are shared among all processes and are initialized to zero. In a concurrent program all the three processes call the barrier function when they need to synchronize globally.
The above implementation of barrier is incorrect. Which one of the following is true?
The barrier implementation is wrong due to the use of binary semaphore S
 
The barrier implementation may lead to a deadlock if two barriers in invocations are used in immediate succession
 
Lines 6 to 10 need not be inside a critical section  
The barrier implementation is correct if there are only two processes instead of three

Hence, it is leads to deadlock.
Question 79 
Barrier is a synchronization construct where a set of processes synchronizes globally i.e. each process in the set arrives at the barrier and waits for all others to arrive and then all processes leave the barrier. Let the number of processes in the set be three and S be a binary semaphore with the usual P and V functions. Consider the following C implementation of a barrier with line numbers shown on left.
void barrier (void) { 1: P(S); 2: process_arrived++; 3. V(S); 4: while (process_arrived !=3); 5: P(S); 6: process_left++; 7: if (process_left==3) { 8: process_arrived = 0; 9: process_left = 0; 10: } 11: V(S); }
The variables process_arrived and process_left are shared among all processes and are initialized to zero. In a concurrent program all the three processes call the barrier function when they need to synchronize globally.
Which one of the following rectifies the problem in the implementation?
Lines 6 to 10 are simply replaced by process_arrived  
At the beginning of the barrier the first process to enter the barrier waits until process_arrived becomes zero before proceeding to execute P(S).
 
Context switch is disabled at the beginning of the barrier and reenabled at the end.
 
The variable process_left is made private instead of shared. 
Question 80 
A CPU has a 32 KB direct mapped cache with 128byte block size. Suppose A is a twodimensional array of size 512×512 with elements that occupy 8bytes each. Consider the following two C code segments, P1 and P2.
P1: for (i=0; i<512; i++) { for (j=0; j<512; j++) { x += A[i][j]; } } P2: for (i=0; i<512; i++) { for (j=0; j<512; j++) { x += A[j][i]; } }
P1 and P2 are executed independently with the same initial state, namely, the array A is not in the cache and i, j, x are in registers. Let the number of cache misses experienced by P1 be M1 and that for P2 be M2.
The value of M1 is:
0  
2048  
16384  
262144 
[P2] Access A in column major order.
No. of cache blocks=Cache size/Block size = 32KB / 128B = 32×2^{10}B / 128B = 2^{15} / 2^{7} = 256
No. of array elements in each block = Block size / Element size = 128B / 8B = 16
Total misses for (P1) = Array size * No. of array elements / No. of cache blocks = (512×512) * 16 / 256 = 16384
Question 81 
A CPU has a 32 KB direct mapped cache with 128byte block size. Suppose A is a twodimensional array of size 512×512 with elements that occupy 8bytes each. Consider the following two C code segments, P1 and P2.
P1: for (i=0; i<512; i++) { for (j=0; j<512; j++) { x += A[i][j]; } } P2: for (i=0; i<512; i++) { for (j=0; j<512; j++) { x += A[j][i]; } }
P1 and P2 are executed independently with the same initial state, namely, the array A is not in the cache and i, j, x are in registers. Let the number of cache misses experienced by P1 be M1 and that for P2 be M2.
The value of the ratio M1/M2 is:
0  
1/16  
1/8  
16 
(for every element there would be a miss)
M1/M2 = 16384/262144 = 1/16
Question 82 
Consider the diagram shown below where a number of LANs are connected by (transparent) bridges. In order to avoid packets looping through circuits in the graph, the bridges organize themselves in a spanning tree. First, the root bridge is identified as the bridge with the least serial number. Next, the root sends out (one or more) data units to enable the setting up of the spanning tree of shortest paths from the root bridge to each bridge.
Each bridge identifies a port (the root port) through which it will forward frames to the root bridge. Port conflicts are always resolved in favour of the port with the lower index value. When there is a possibility of multiple bridges forwarding to the same LAN (but not through the root port), ties are broken as follows: bridges closest to the root get preference and between such bridges, the one with the lowest serial number is preferred.
For the given connection of LANs by bridges, which one of the following choices represents the depth first traversal of the spanning tree of bridges?
B1, B5, B3, B4, B2  
B1, B3, B5, B2, B4  
B1, B5, B2, B3, B4  
B1, B3, B4, B5, B2 
B5 is connected to port 1 of B1 so B5 will be traversed after B1.
Port1 of B5 is connected to port1 of B2 and port2 of B3.
B2 is connected with lower index port so B2 is traversed next.
Port 2 Both B3 and B4 is connected with port1 of B2, but B3 is Closer to root so B3 will be traversed next.
Depth First traversal is B1, B5, B2, B3, B4.
Question 83 
Consider the diagram shown below where a number of LANs are connected by (transparent) bridges. In order to avoid packets looping through circuits in the graph, the bridges organize themselves in a spanning tree. First, the root bridge is identified as the bridge with the least serial number. Next, the root sends out (one or more) data units to enable the setting up of the spanning tree of shortest paths from the root bridge to each bridge.
Each bridge identifies a port (the root port) through which it will forward frames to the root bridge. Port conflicts are always resolved in favour of the port with the lower index value. When there is a possibility of multiple bridges forwarding to the same LAN (but not through the root port), ties are broken as follows: bridges closest to the root get preference and between such bridges, the one with the lowest serial number is preferred.
Consider the correct spanning tree for the previous question. Let host H1 send out a broadcast ping packet. Which of the following options represents the correct forwarding table on B3?
Question 84 
Which one of the following grammars generates the language L = {a^{i}b^{j}i≠j}?
S→ACCB C→aCbab A→aAϵ B→Bbϵ  
S→aSSbab  
S→ACCB C→aCbϵ A→aAϵ B→Bbϵ  
S→ACCB C→aCbϵ A→aAa B→Bbb 
Question 85 
In the correct grammar of above question, what is the length of the derivation (number of steps starting from S) to generate the string a^{l}b^{m} with l≠m?
max(l,m)+2  
l+m+2  
l+m+3  
max(l, m)+3 
S → ACCB C → aCbϵ A → aAa B → Bbb
Assume a string: “aaabb” in this l=3 and m=2
The steps are:
Step1: S> AC
Step 2: S> aC By production: A> a
Step 3: S> aaCb By production: C> aCb
Step 4: S> aaaCbb By production: C> aCb
Step 5: S> aaabb By production: C> ϵ
Hence, it is clear that the correct option is A, i.e. max(l,m)+2