2009
Question 1 
Which one of the following in NOT necessarily a property of a Group?
Commutativity
 
Associativity  
Existence of inverse for every element
 
Existence of identity

Question 1 Explanation:
A Group should satisfy Closure, Associative, should have identity element and each element has inverse.
So, commutativity is not required.
So, commutativity is not required.
Question 2 
What is the chromatic number of an nvertex simple connected graph which does not contain any odd length cycle? Assume n ≥ 2.
2  
3  
n1  
n 
Question 2 Explanation:
If n≥ 2 and there are no odd length cycles, Then it is bipartite graph.
A bipartite graph has the chromatic number 2.
Eg: Consider a square, which has 4 edges. It can be represented as bipartite ,with chromatic number 2.
Eg: Consider a square, which has 4 edges. It can be represented as bipartite ,with chromatic number 2.
Question 3 
Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices?
No two vertices have the same degree.
 
At least two vertices have the same degree.  
At least three vertices have the same degree.  
All vertices have the same degree.

Question 3 Explanation:
Method 1:
If all vertices have different degrees, then the degree sequence will be {1,2,3,....n1}, it will not have ‘n’( A simple graph will not have edge to itself, so it can have edges with all other (n1) vertices). Degree sequence has only (n1) numbers, but we have ‘n’ vertices. So, by Pigeonhole principle there are two vertices which has same degree.
Method 2:
A) consider a triangle, all vertices has same degree, so it is false
C) consider a square with one diagonal, there are less than three vertices with same degree, so it is false
D) consider a square with one diagonal, vertices have different degrees. So, it is false.
We can conclude that option B is correct.
If all vertices have different degrees, then the degree sequence will be {1,2,3,....n1}, it will not have ‘n’( A simple graph will not have edge to itself, so it can have edges with all other (n1) vertices). Degree sequence has only (n1) numbers, but we have ‘n’ vertices. So, by Pigeonhole principle there are two vertices which has same degree.
Method 2:
A) consider a triangle, all vertices has same degree, so it is false
C) consider a square with one diagonal, there are less than three vertices with same degree, so it is false
D) consider a square with one diagonal, vertices have different degrees. So, it is false.
We can conclude that option B is correct.
Question 4 
Consider the binary relation R = {(x, y), (x, z), (z, x), (z, y)} on the set {x, y, z}. Which one of the following is TRUE?
R is symmetric but NOT antisymmetric
 
R is NOT symmetric but antisymmetric
 
R is both symmetric and antisymmetric
 
R is neither symmetric nor antisymmetric

Question 4 Explanation:
Symmetric Relation: A relation R on a set A is called symmetric if (b,a) € R holds when (a,b) € R.
Antisymmetric Relation: A relation R on a set A is called antisymmetric if (a,b)€ R and (b,a) € R then a = b is called antisymmetric.
In the given relation R, for (x,y) there is no (y,x). So, this is not Symmetric. (x,z) is in R also (z,x) is in R, but as per antisymmetric relation, x should be equal to z, where this fails.
So, R is neither Symmetric nor Antisymmetric.
Antisymmetric Relation: A relation R on a set A is called antisymmetric if (a,b)€ R and (b,a) € R then a = b is called antisymmetric.
In the given relation R, for (x,y) there is no (y,x). So, this is not Symmetric. (x,z) is in R also (z,x) is in R, but as per antisymmetric relation, x should be equal to z, where this fails.
So, R is neither Symmetric nor Antisymmetric.
Question 5 
(1217)_{8} is equivalent to
(1217)_{16}
 
(028F)_{16}
 
(2297)_{10}
 
(0B17)_{16} 
Question 5 Explanation:
(1217)_{8}= (001 010 001 111)_{2}
Divide the bits into groups, each containing 4 bits.
=(0010 1000 1111)_{2}
=(28F)_{16}
Divide the bits into groups, each containing 4 bits.
=(0010 1000 1111)_{2}
=(28F)_{16}
Question 6 
What is the minimum number of gates required to implement the Boolean function (AB+C) if we have to use only 2input NOR gates?
2  
3  
4  
5 
Question 6 Explanation:
NOR is Complement of OR
AB+C
= (A+C)(B+C) ← Distribution of + over
= ((A+C)’+(B+C)’)’
1st NOR (A+C)’. Let X = (A+C)’
2nd NOR (B+C)’. Let Y = (B+C)’
3rd NOR (X+Y)’
AB+C
= (A+C)(B+C) ← Distribution of + over
= ((A+C)’+(B+C)’)’
1st NOR (A+C)’. Let X = (A+C)’
2nd NOR (B+C)’. Let Y = (B+C)’
3rd NOR (X+Y)’
Question 7 
How many 32K × 1 RAM chips are needed to provide a memory capacity of 256Kbytes?
8  
32  
64  
128 
Question 7 Explanation:
Each chip capacity = 32K×1 bit
Needed memory capacity = 256Kbytes = 256K*8 bits
Number of chips needed = 256K*8 / 32K×1= 64
Needed memory capacity = 256Kbytes = 256K*8 bits
Number of chips needed = 256K*8 / 32K×1= 64
Question 8 
A CPU generally handles an interrupt by executing an interrupt service routine
As soon as an interrupt is raised.  
By checking the interrupt register at the end of fetch cycle.  
By checking the interrupt register after finishing the execution of the current instruction.  
By checking the interrupt register at fixed time intervals. 
Question 8 Explanation:
As soon as an interrupt is raised the corresponding register is set. But CPU acts on it only after execution of its current instruction. This is followed to ensure integrity of instructions.
Question 9 
In which one of the following page replacement policies, Belady’s anomaly may occur?
FIFO
 
Optimal
 
LRU  
MRU

Question 9 Explanation:
Bélády's anomaly is the phenomenon in which increasing the number of page frames results in an increase in the number of page faults for certain memory access patterns. This phenomenon is commonly experienced when using the firstin firstout.
Question 10 
The essential content(s) in each entry of a page table is / are
Virtual page number  
Page frame number
 
Both virtual page number and page frame number
 
Access right information

Question 10 Explanation:
For every page table it contains page frame number.
Virtual page number can represents index in the page table to get the page frame number.
Virtual page number can represents index in the page table to get the page frame number.
Question 11 
What is the number of swaps required to sort n elements using selection sort, in the worst case?
θ(n)
 
θ(n log n)
 
θ(n^{2})  
θ(n^{2} logn)

Question 11 Explanation:
Selection sort – There is no Worst case input for selection sort. Since it searches for the index of kth minimum element in kth iteration and then in one swap, it places that element into its correct position. For n1 iterations of selection sort, it can have O(n) swaps. Selection Sort does a significant number of comparisons before moving each element directly to its final intended position. At most the algorithm requires N swaps. once we swap an element into place, you never go back again.So it is great for writes O(n) but not so great (at all) for reads — O(n^{2}). It isn’t wellsuited to generalized sorting, but might work well in specialized situations like EEPROM (where writes are inordinately expensive).
Question 12 
S → aSabSbab; The language generated by the above grammar over the alphabet {a,b} is the set of
All palindromes.  
All odd length palindromes.  
Strings that begin and end with the same symbol.  
All even length palindromes. 
Question 12 Explanation:
From the grammar, we can easily infer that it generates all the palindromes of odd length, for ex: strings {aba, bab, aaa, bbb, ….}
Question 13 
P Only  
Q Only
 
Both P and Q
 
Neither P nor Q

Question 13 Explanation:
BellmanFord shortest path algorithm is a single source shortest path algorithm. So it can only find cycles which are reachable from a given source, not any negative weight cycle. Consider a disconnected where a negative weight cycle is not reachable from the source at all. If there is a negative weight cycle, then it will appear in shortest path as the negative weight cycle will always form a shorter path when iterated through the cycle again and again.
More Info: The Dijkstra'a algorithm:
A greedy algorithm
Works when weights are all nonnegative
The bellman ford algorithm: If there is a negative cycle, there is no solution, but negative weight edges are allowed.
– Add this cycle again can always produces a less weight path
If there is no negative cycle, a shortest path has at most V1 edges
A dynamic programming algorithm
Note: Dijkastra is faster than BellmanFord
More Info: The Dijkstra'a algorithm:
A greedy algorithm
Works when weights are all nonnegative
The bellman ford algorithm: If there is a negative cycle, there is no solution, but negative weight edges are allowed.
– Add this cycle again can always produces a less weight path
If there is no negative cycle, a shortest path has at most V1 edges
A dynamic programming algorithm
Note: Dijkastra is faster than BellmanFord
Question 14 
Let π_{A} be a problem that belongs to the class NP. Then which one of the following is TRUE?
There is no polynomial time algorithm for π_{A}.
 
If π_{A} can be solved deterministically in polynomial time,then P = NP.  
If π_{A} is NPhard, then it is NPcomplete.  
π_{A} may be undecidable. 
Question 14 Explanation:
As per the above question, only option C is correct because it is an standard definition of NP Complete. Rest of the options are violating their definition and properties.
NPComplete: In computational complexity theory, an NPcomplete decision problem is one belonging to both the NP and the NPhard complexity classes. In this context, NP stands for "nondeterministic polynomial time". The set of NPcomplete problems is often denoted by NPC or NPC.
Standard Definition:
A decision problem C is NPcomplete if:
1. C is in NP, and
2. Every problem in NP is reducible to C in polynomial time.
C can be shown to be in NP by demonstrating that a candidate solution to C can be verified in polynomial time. Note that a problem satisfying condition 2 is said to be NPhard, whether or not it satisfies condition 1. A consequence of this definition is that if we had a polynomial time algorithm (on a UTM, or any other Turingequivalent abstract machine) for C, we could solve all problems in NP in polynomial time.
Note: As per Present GATE syllabus NP Complete and NP Hard not required
NPComplete: In computational complexity theory, an NPcomplete decision problem is one belonging to both the NP and the NPhard complexity classes. In this context, NP stands for "nondeterministic polynomial time". The set of NPcomplete problems is often denoted by NPC or NPC.
Standard Definition:
A decision problem C is NPcomplete if:
1. C is in NP, and
2. Every problem in NP is reducible to C in polynomial time.
C can be shown to be in NP by demonstrating that a candidate solution to C can be verified in polynomial time. Note that a problem satisfying condition 2 is said to be NPhard, whether or not it satisfies condition 1. A consequence of this definition is that if we had a polynomial time algorithm (on a UTM, or any other Turingequivalent abstract machine) for C, we could solve all problems in NP in polynomial time.
Note: As per Present GATE syllabus NP Complete and NP Hard not required
Question 15 
Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?
The set of all strings containing the substring 00.
 
The set of all strings containing at most two 0’s.
 
The set of all strings containing at least two 0’s.
 
The set of all strings that begin and end with either 0 or 1.

Question 15 Explanation:
Option A is false, as the regular expression generates string “010” which doesn’t have “00” as substring. Option B is false, as we can have the string “000” from the given regular expression, which has more than two 0’s. Option D is false, as we cannot generate the string “01” from the given regular expression and according to option D, string “01” must be generated by regular expression, which clearly shows option D is not correct language as per regular expression.
Question 16 
Which one of the following is FALSE?
There is unique minimal DFA for every regular language.  
Every NFA can be converted to an equivalent PDA.  
Complement of every contextfree language is recursive.
 
Every nondeterministic PDA can be converted to an equivalent deterministic PDA.

Question 16 Explanation:
As we know there are several languages (CFL) for which we only have NPDA, i.e. these languages cannot be recognized by DPDA. For example
L= {ww^{r}  w ϵ {a,b}* } is a CFL but not DCFL, i.e. it can be recognized by NPDA but not by DPDA.
L= {ww^{r}  w ϵ {a,b}* } is a CFL but not DCFL, i.e. it can be recognized by NPDA but not by DPDA.
Question 17 
P4, Q1, R2, S3
 
P3, Q1, R4, S2
 
P3, Q4, R1, S2  
P2, Q1, R4, S3

Question 17 Explanation:
Lexical analysis phase uses regular expression to identify the pattern of tokens, PDA is used in CFG and hence syntax analysis phase is related to PDA. Data flow analysis is done in code optimization phase and register allocation is related to code generation phase.
Question 18 
6  
8  
14  
15 
Question 18 Explanation:
int x=15;
printf(fun(5,&x));
The code is implemented using Tail Recursion.
fun(5,15)
↓
fun(4,15)
↓
fun(3,15)
↓
fun(2,15)
↓
fun(1,15)
→ First we will trace fun(1,15) which returns 1.
→ Then trace fun(2,15) using fun(1,15) value, it returns 2.
→ Then fun(3,15), it returns 3≃(1+2)
→ Then fun(4,15), it returns 5=(2+3)
→ Then fun(5,15), it returns 8=(3+5)
If you call fun(6,15) then it will return 13=(5+8)
Here fun(n,*x)≃fun(n1,&x)+fun(n2,&x), where fun(n1,&x) is storing in variable ‘t’ & fun(n2,&x) is storing in variable x(*fp).
∴ The program is nth Fibonacci number.
printf(fun(5,&x));
The code is implemented using Tail Recursion.
fun(5,15)
↓
fun(4,15)
↓
fun(3,15)
↓
fun(2,15)
↓
fun(1,15)
→ First we will trace fun(1,15) which returns 1.
→ Then trace fun(2,15) using fun(1,15) value, it returns 2.
→ Then fun(3,15), it returns 3≃(1+2)
→ Then fun(4,15), it returns 5=(2+3)
→ Then fun(5,15), it returns 8=(3+5)
If you call fun(6,15) then it will return 13=(5+8)
Here fun(n,*x)≃fun(n1,&x)+fun(n2,&x), where fun(n1,&x) is storing in variable ‘t’ & fun(n2,&x) is storing in variable x(*fp).
∴ The program is nth Fibonacci number.
Question 20 
〈2, 2, 3〉 and 〈2, 3, 2〉  
〈2, 2, 3〉 and 〈2, 2, 3〉
 
〈2, 3, 2〉 and 〈2, 3, 2〉  
〈2, 3, 2〉 and 〈2, 2, 3〉 
Question 21 
0.453
 
0.468
 
0.485  
0.492

Question 21 Explanation:
P(0) = Probability of getting odd no. face.
P(e) = Probability of getting even no. face.
It is given that,
P(0) = 0.9 P(e)  (I)
Also we know that,
P(0) + P(e) = 1  (II)
Solving equation (I) and (II) we get,
P(e) = 0.52
Also even no. can be 2 or 4 or 6.
And given in question that P(2) = P(4) = P(6).
So, 3 × P(2) = 0.52
P(2) = 0.175
So, P(2) = P(4) = P(6) = 0.175
Also in question it is given that,
P(e/>3) = 0.75
P(even no. greater than 3)/ P(no. greater than 3) = 0.75
P(4,6)/P(>3) = 0.75
(0.175×2)/P(>3) = 0.75
P(>3) = 0.35/0.75 = 0.467
P(e) = Probability of getting even no. face.
It is given that,
P(0) = 0.9 P(e)  (I)
Also we know that,
P(0) + P(e) = 1  (II)
Solving equation (I) and (II) we get,
P(e) = 0.52
Also even no. can be 2 or 4 or 6.
And given in question that P(2) = P(4) = P(6).
So, 3 × P(2) = 0.52
P(2) = 0.175
So, P(2) = P(4) = P(6) = 0.175
Also in question it is given that,
P(e/>3) = 0.75
P(even no. greater than 3)/ P(no. greater than 3) = 0.75
P(4,6)/P(>3) = 0.75
(0.175×2)/P(>3) = 0.75
P(>3) = 0.35/0.75 = 0.467
Question 22 
a, b are generators
 
b, c are generators
 
c, d are generators
 
d, a are generators

Question 22 Explanation:
Each element of set can be written as a power of g in multiplicative notation, or as a multiple of g in additive notation. This element g is called a generator of the group.
We can observe that, a is an identity element. ( a *x = x ). An identity element cannot be a generator, as it cannot produce any other element ( always a*a*... = a).
Also, b*b =a, so it also cannot produce all other elements ( always b*b*... =a , where a is identify element).
c,d are able to produce other elements like { c*c =b, c*(c*c) = c*b= d, c*(c*(c*c))) = c*(c*b)= c*d=a. }. Similar with d.
We can observe that, a is an identity element. ( a *x = x ). An identity element cannot be a generator, as it cannot produce any other element ( always a*a*... = a).
Also, b*b =a, so it also cannot produce all other elements ( always b*b*... =a , where a is identify element).
c,d are able to produce other elements like { c*c =b, c*(c*c) = c*b= d, c*(c*(c*c))) = c*(c*b)= c*d=a. }. Similar with d.
Question 23 
∀x(P(x) → (G(x) ∧ S(x)))
 
∀x((G(x) ∧ S(x)) → P(x))  
∃x((G(x) ∧ S(x)) → P(x)
 
∀x((G(x) ∨ S(x)) → P(x))

Question 23 Explanation:
Interpreting the options will lead to
(A) for all ornaments, if it is precious then they should be gold and silver.
But, given statement does not says that, “ only gold and silver are precious “ . So this is wrong.
(B) For all ornaments, which contains gold and silver are precious.
Which is only the shaded region in the venn diagrams. But, it misses p,r regions. So, this is wrong option.
C) Some ornaments, which are gold and silver are precious. It is false, because all gold or silver ornaments are precious.
D) For all ornaments, Any ornament which is gold or silver is precious. Which is true.
(A) for all ornaments, if it is precious then they should be gold and silver.
But, given statement does not says that, “ only gold and silver are precious “ . So this is wrong.
(B) For all ornaments, which contains gold and silver are precious.
Which is only the shaded region in the venn diagrams. But, it misses p,r regions. So, this is wrong option.
C) Some ornaments, which are gold and silver are precious. It is false, because all gold or silver ornaments are precious.
D) For all ornaments, Any ornament which is gold or silver is precious. Which is true.
Question 24 
¬Q□¬P
 
P□¬Q
 
¬P□Q
 
¬P□¬Q

Question 24 Explanation:
The options are simple to draw the truth table then go with the corresponding options.
P∨Q=P□️Q
So, option B is correct.
P∨Q=P□️Q
So, option B is correct.
Question 26 
I and III  
I and IV
 
II and III
 
II and IV

Question 26 Explanation:
I) ¬∀x(P(x)) = ∃x(¬P(x)) [De morgan's Law]
II ) ¬∃x(P(x))= ∀x(~P(x))
III) ¬∃x(¬P(x)) = ∀x(P(x))
II ) ¬∃x(P(x))= ∀x(~P(x))
III) ¬∃x(¬P(x)) = ∀x(P(x))
Question 27 
3  
4  
5  
6 
Question 27 Explanation:
Consider the below given FSM (represented as graph)
From the given FSM we can clearly see that, if we start from initial state (00) and follow the input “101” {highlighted in RED color},
{state 00, 1} > state “01” , output 0,
{state 01, 0} > state “10” , output 0,
{state 10, 1} > state “01” , output 1,
Hence it require an input string of minimum length 3, which will take the machine to the state A=0, B=1 with Output = 1.
From the given FSM we can clearly see that, if we start from initial state (00) and follow the input “101” {highlighted in RED color},
{state 00, 1} > state “01” , output 0,
{state 01, 0} > state “10” , output 0,
{state 10, 1} > state “01” , output 1,
Hence it require an input string of minimum length 3, which will take the machine to the state A=0, B=1 with Output = 1.
Question 29 
3  
8  
129  
216 
Question 29 Explanation:
It is given that cache contains 16 blocks, it is 4way set associative cache.
So number of sets = 16 / 4 = 4
Given main memory blocks will be mapped to one of the 4 sets.
The given blocks are 0, 255, 1, 4, 3, 8, 133, 159, 216, 129, 63, 8, 48, 32, 73, 92, 155, and they will be mapped to following sets(Since there are 4 sets we get the set number by doing mod 4):
0, 3, 1, 0, 3, 0, 1, 3, 0, 1, 3, 0, 0, 0, 1, 0, 3
The cache mapping and the replacement using LRU can be seen from the below diagram.
We can see that at the end of mapping the given block pattern block number 216 is not in the cache.
So number of sets = 16 / 4 = 4
Given main memory blocks will be mapped to one of the 4 sets.
The given blocks are 0, 255, 1, 4, 3, 8, 133, 159, 216, 129, 63, 8, 48, 32, 73, 92, 155, and they will be mapped to following sets(Since there are 4 sets we get the set number by doing mod 4):
0, 3, 1, 0, 3, 0, 1, 3, 0, 1, 3, 0, 0, 0, 1, 0, 3
The cache mapping and the replacement using LRU can be seen from the below diagram.
We can see that at the end of mapping the given block pattern block number 216 is not in the cache.
Question 30 
All processes will finish without any deadlock.  
Only P1 and P2 will be in deadlock.
 
Only P1 and P3 will be in a deadlock.
 
All three processes will be in deadlock. 
Question 30 Explanation:
Process P_{1}:
t=0; req R_{2}2
t=1; req R_{3}1
t=3; req R_{1}2
t=5; release R_{2}1
& R_{1}1
t=7; release R_{3}1
t=8; req R_{4}2
t=10; finish:After completion of P, it releases all the resources.
Process P_{2}:
t=0; req R_{3}2
t=2; req R_{4}1
t=4; req R_{1}1
t=6; releases R_{3}1
t=8; finishes
It releases all the resources.
Process P_{3}:
t=0; req R_{4}1
t=2; req R_{1}2
t=5; releases R_{1}2
t=7; req R_{2}1
t=8; req R_{3}1
t=9; finishes
It releases all the resources.
All processes will finish without any deadlock.
t=0; req R_{2}2
t=1; req R_{3}1
t=3; req R_{1}2
t=5; release R_{2}1
& R_{1}1
t=7; release R_{3}1
t=8; req R_{4}2
t=10; finish:After completion of P, it releases all the resources.
Process P_{2}:
t=0; req R_{3}2
t=2; req R_{4}1
t=4; req R_{1}1
t=6; releases R_{3}1
t=8; finishes
It releases all the resources.
Process P_{3}:
t=0; req R_{4}1
t=2; req R_{1}2
t=5; releases R_{1}2
t=7; req R_{2}1
t=8; req R_{3}1
t=9; finishes
It releases all the resources.
All processes will finish without any deadlock.
Question 31 
95 ms  
119 ms
 
233 ms  
276 ms

Question 31 Explanation:
The given sequence is
4, 34, 10,7, 19, 73, 2, 15, 6, 20
Arrange the sequence in order
2, 4, 6, 10, 15, 19, 20, 34, 73
⇒ 1 ms to move from one cylinder to adjacent one
⇒ (16*1)+(14*1)+(1*1)+(4*1)+(5*1)+(3*1)+(1*1)+(2*1)+(2*1)+(71*1)
⇒ 16+14+1+4+5+3+1+2+2+71
⇒ 119 ms
4, 34, 10,7, 19, 73, 2, 15, 6, 20
Arrange the sequence in order
2, 4, 6, 10, 15, 19, 20, 34, 73
⇒ 1 ms to move from one cylinder to adjacent one
⇒ (16*1)+(14*1)+(1*1)+(4*1)+(5*1)+(3*1)+(1*1)+(2*1)+(2*1)+(71*1)
⇒ 16+14+1+4+5+3+1+2+2+71
⇒ 119 ms
Question 32 
I and II
 
I and III
 
II and III  
II and IV

Question 32 Explanation:
Statement I is false, if a process makes a transition D, then it result to perform a transition B immediately not A.
Statement II is true, a process can move to ready state when I/O completes irrespective of other process being in running state or not.
Statement III is true, the transition C, represents preemptive scheduling.
Statement IV is false, because it is preemptive scheduling.
Correct Answer is OptionC (II & III are true).
Statement II is true, a process can move to ready state when I/O completes irrespective of other process being in running state or not.
Statement III is true, the transition C, represents preemptive scheduling.
Statement IV is false, because it is preemptive scheduling.
Correct Answer is OptionC (II & III are true).
Question 33 
I only
 
I and II  
II and III
 
IV only 
Question 33 Explanation:
The given solution is the basic testandset solution. So there is no possibility of getting deadlock.
It is not using any queue to avoid starvation and there is no use of FIFO.
In CS, only one process can enter.
So, Answer is option A.
It is not using any queue to avoid starvation and there is no use of FIFO.
In CS, only one process can enter.
So, Answer is option A.
Question 34 
A multilevel page table is preferred in comparison to a single level page table for translating virtual address to physical address because
It reduces the memory access time to read or write a memory location.
 
It helps to reduce the size of page table needed to implement the virtual address space of a process.
 
It is required by the translation lookaside buffer.
 
It helps to reduce the number of page faults in page replacement algorithms.

Question 34 Explanation:
In multilevel page table size is too big to fit in contiguous space then page tables are to be divided into different levels.
Question 35 
θ(n)
 
θ(n log n)  
θ(n^{2})
 
θ(n^{2}log n ) 
Question 35 Explanation:
The above recurrence relation is form of master theorem. So, we can apply directly master's theorem T(n) = aT(n/b) + n^{k} log^{p} n)
The recurrence relation is T(n) = T(n/3) + cn
Here a=1 , b=3, k=1, p=0.
So, ak and p>=0. So, it comes under case 3.
Therefore T(n) = θ(n^{k}(log^{p}n)) => θ(n^{1}(log^{0} n)) => θ(n)
The recurrence relation is T(n) = T(n/3) + cn
Here a=1 , b=3, k=1, p=0.
So, ak and p>=0. So, it comes under case 3.
Therefore T(n) = θ(n^{k}(log^{p}n)) => θ(n^{1}(log^{0} n)) => θ(n)
Question 36 
The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?
Question 36 Explanation:
Given keys: 12, 18, 13, 2, 3, 23, 5 & 15
They are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k)=k mod 10 & linear probing is used.
12 % 10 = 2
18 % 10 = 8
13 % 10 = 3
2 % 10 = 2 (Index 4 is empty)
3 % 10 = 3 (Index 5 is empty)
23 % 10 = 3 (Index 6 is empty)
5 % 10 = 5 (Index 7 is empty)
15 % 10 = 5 (Index 9 is empty)
Hence Option C is correct.
A & B doesn’t include all the keys & option D is similar to chaining. So, will go with C.
They are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k)=k mod 10 & linear probing is used.
12 % 10 = 2
18 % 10 = 8
13 % 10 = 3
2 % 10 = 2 (Index 4 is empty)
3 % 10 = 3 (Index 5 is empty)
23 % 10 = 3 (Index 6 is empty)
5 % 10 = 5 (Index 7 is empty)
15 % 10 = 5 (Index 9 is empty)
Hence Option C is correct.
A & B doesn’t include all the keys & option D is similar to chaining. So, will go with C.
Question 37 
What is the maximum height of any AVLtree with 7 nodes? Assume that the height of a tree with a single node is 0.
2  
3  
4  
5 
Question 37 Explanation:
The maximum height of any AVL tree with 7 nodes is, [where root is considered as height 0]
2^{h}1=7
∴ h=3
2^{h}1=7
∴ h=3
Question 38 
(b,e)(e,f)(a,c)(b,c)(f,g)(c,d)
 
(b,e)(e,f)(a,c)(f,g)(b,c)(c,d)
 
(b,e)(a,c)(e,f)(b,c)(f,g)(c,d)  
(b,e)(e,f)(b,c)(a,c)(f,g)(c,d) 
Question 38 Explanation:
To find Minimum Spanning Tree(MST) using Kruskal’s algorithm we have to follow standard procedure is
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.
As per the options below Option A,B,C, are following correct order but Option D is violating Kruskal’s procedure. The edge between ac of weight 4 comes after bc of weight 3.
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.
As per the options below Option A,B,C, are following correct order but Option D is violating Kruskal’s procedure. The edge between ac of weight 4 comes after bc of weight 3.
Question 39 
In quick sort, for sorting n elements, the (n/4)^{th} smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?
θ(n)
 
θ(n log n)
 
θ(n^{2})
 
θ(n^{2} log n ) 
Question 39 Explanation:
n→n/(4/3)→n/(4/3)^{2}→n/(4/3)^{3}n/(4/3)^{k}=1
n/(4/3)^{k}=1
⇒n=(4/3)^{k}⇒k=log_{4/3}n [k=no. of levels]
In each level workdone = Cn
So, total workdone = Cn⋅log_{4/3}n=(nlog_{4/3}n)
Question 40 
Not recursive
 
Regular
 
Context free but not regular  
Recursively enumerable but not context free 
Question 40 Explanation:
The strings in L_{1} are { c, abc, cab, abcab, aabbcab, abcaabb, aabbcaabb,.....} and the strings in L_{2} are { ϵ, a, b, c, ab, bc, ac, abc, aabc, abbc, abcc, aabbcc, …..}
Clearly, L_{1} ∩ L_{2} is {a^{x}b^{x}  x ≥0}, which is CFL but not regular.
Clearly, L_{1} ∩ L_{2} is {a^{x}b^{x}  x ≥0}, which is CFL but not regular.
Question 41 
begin either with 0 or 1
 
end with 0
 
end with 00  
contain the substring 00 
Question 41 Explanation:
Option A is false, as the DFA is not accepting the string “10”, option B is false as the DFA is not accepting the string “10” . Option D is false as the DFA doesn’t accept the string “1001” which has “00” as substring. Hence option C , every strings end with “00” is correct.
Question 42 
I and II
 
I and IV
 
III and IV
 
I, III and IV 
Question 42 Explanation:
Statement II is false, as a programming language which allows recursion requires dynamic storage allocation. Statement III is false, as Lattributed definition (assume for instance the Lattributed definition has synthesized attribute only) can be evaluated in bottom up framework.
Statement I is true, as the bottom up and top down parser take O(n) time to parse the string , i.e. only one scan of input is required.
Statement IV is true,Code improving transformations can be performed at both source language and intermediate code level. For example implicit type casting is also a kind of code improvement which is done during semantic analysis phase and intermediate code optimization is a topic itself which uses various techniques to improve the code such as loop unrolling, loop invariant.
Statement I is true, as the bottom up and top down parser take O(n) time to parse the string , i.e. only one scan of input is required.
Statement IV is true,Code improving transformations can be performed at both source language and intermediate code level. For example implicit type casting is also a kind of code improvement which is done during semantic analysis phase and intermediate code optimization is a topic itself which uses various techniques to improve the code such as loop unrolling, loop invariant.
Question 43 
S_{1} and S_{2}  
S_{2} and S_{3}  
S_{3} only
 
S_{4} only 
Question 43 Explanation:
S_{1} has a cycle from T_{1}→T_{2} and T_{2}→T_{1}
Schedule S_{2},
Dependency graph is,
So, there is no cycle.
Schedule S3,
Dependency graph is,
S_{4} also has a cycle T_{1}→T_{2} and T_{2}→T_{1}.
So, S_{2} and S_{3} are conflict serializable.
Dependency graph is,
So, there is no cycle.
Schedule S3,
Dependency graph is,
S_{4} also has a cycle T_{1}→T_{2} and T_{2}→T_{1}.
So, S_{2} and S_{3} are conflict serializable.
Question 44 
2  
3  
4  
5 
Question 44 Explanation:
Insert 10:
Insert 3:
Insert 6:
Insert 4:
Insert 2:
Insert 1:
So, total splits are 3.
Insert 3:
Insert 6:
Insert 4:
Insert 2:
Insert 1:
So, total splits are 3.
Question 45 
I and II
 
I and III
 
II and IV  
III and IV 
Question 45 Explanation:
R={a,b,c}
S={c}
It looks like Division operator. Since a division operator in E(A,B)/ P(B) will be equal to
Now replacing A=RS P=r
B=S
E=r
we will get,
equivalent to I
∴ It is equivalent to division operator.
⇒ r(RS,S)/r(S)
This logical statement means that
① Select t(RS) from r such that
② for all tuples U in S,
③ there exists a tuple V in r, such that
④ U=V[S] & t=V[RS]
A(x,y) & B(y)
A/B = {(x)  ∃(x,y)∈A(y)∈B}
which means that A/B contains all x tuples, such that for every tuple in B, there is an xy tuple in A.
So, this is just equivalent to I.
This logical statement means that
① Select t(RS) from r such that
② for all tuples V in r,
③ there exists a tuple U in r, such that
④ U=V[S] & t=V[RS]
⇒ Select (RS) values from r, where the S value is in (r/r), which will be true only if S in r is a foreign key referring to S is r.
This selects (a,b) from all tuples from r which has an equivalent value in S.
S={c}
It looks like Division operator. Since a division operator in E(A,B)/ P(B) will be equal to
Now replacing A=RS P=r
B=S
E=r
we will get,
equivalent to I
∴ It is equivalent to division operator.
⇒ r(RS,S)/r(S)
This logical statement means that
① Select t(RS) from r such that
② for all tuples U in S,
③ there exists a tuple V in r, such that
④ U=V[S] & t=V[RS]
A(x,y) & B(y)
A/B = {(x)  ∃(x,y)∈A(y)∈B}
which means that A/B contains all x tuples, such that for every tuple in B, there is an xy tuple in A.
So, this is just equivalent to I.
This logical statement means that
① Select t(RS) from r such that
② for all tuples V in r,
③ there exists a tuple U in r, such that
④ U=V[S] & t=V[RS]
⇒ Select (RS) values from r, where the S value is in (r/r), which will be true only if S in r is a foreign key referring to S is r.
This selects (a,b) from all tuples from r which has an equivalent value in S.
Question 46 
I and II
 
I and III
 
II and IV  
III and IV 
Question 46 Explanation:
To generate the encryption and decryption keys, we can proceed as follows.
1. Generate randomly two “large” primes p and q.
2. Compute n=pq and ∅=(p1)(q1).
3. Choose a number e so that
gcd(e,∅)=1
4. Find the multiplicative inverse of e modulo ∅, i.e., find d so that
ed≡1 (mod ∅)
This can be done efficiently using Euclid’s Extended Algorithm.
The encryption public key is K_{E}=(n,e) and the decryption private key is K_{D}=(n,d).
The encryption function is
E(M)=M^{e} mod n
The decryption function is
D(M)=M^{d} mod n
1. Generate randomly two “large” primes p and q.
2. Compute n=pq and ∅=(p1)(q1).
3. Choose a number e so that
gcd(e,∅)=1
4. Find the multiplicative inverse of e modulo ∅, i.e., find d so that
ed≡1 (mod ∅)
This can be done efficiently using Euclid’s Extended Algorithm.
The encryption public key is K_{E}=(n,e) and the decryption private key is K_{D}=(n,d).
The encryption function is
E(M)=M^{e} mod n
The decryption function is
D(M)=M^{d} mod n
Question 47 
0.015/s
 
0.064/s
 
0.135/s  
0.327/s

Question 47 Explanation:
32 bits are used to represent a sequence number. So we have 2^{32} different sequence number.
The maximum packet lifetime is given is given 64s.
Maximum data rate possible(bandwidth) to avoid the wraparound = 2^{32}/64 = 2^{26} Byte/sec.
The clock counter increments once per milliseconds = That means when then counter increments next possible sequence number is generated. The packet lifetime is 64 seconds and after this 64 seconds next sequence number is come. So that means in this 64 seconds only 1 sequence number is generated.
Hence the minimum rate is = 1/64 = 0.015/sec.
The maximum packet lifetime is given is given 64s.
Maximum data rate possible(bandwidth) to avoid the wraparound = 2^{32}/64 = 2^{26} Byte/sec.
The clock counter increments once per milliseconds = That means when then counter increments next possible sequence number is generated. The packet lifetime is 64 seconds and after this 64 seconds next sequence number is come. So that means in this 64 seconds only 1 sequence number is generated.
Hence the minimum rate is = 1/64 = 0.015/sec.
Question 48 
Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to detect odd number of bits in error?
G(x) contains more than two terms  
G(x) does not divide 1+x^{k}, for any k not exceeding the frame length
 
1+x is a factor of G(x)
 
G(x) has an odd number of terms 
Question 48 Explanation:
Odd number of bit errors can be detected if G(x) contains (x+1) as a factor.
Question 51 
505035  
505036  
505037  
505038 
Question 51 Explanation:
By default the cylinders numbering starts from 0. In the given hard disk there are 1000 cylinders, 1st cylinder is numbered 0, 2nd cylinder is numbered 1 and so on 1000th cylinder is numbered 999.
To reach a cylinder numbered n, we need to cross cylinders numbered from 0 to n1.
To reach cylinder numbered 400 (401th cylinder) we need to skip cylinders numbered from 0 to 399, (from cylinder number 0 to 399 there are total 400 cylinders).
Each cylinder consists of 10 plates with 2 recording surfaces and 63 sectors per track.
So total number of tracks to be crossed to reach cylinder numbered 400 = 400 * (10*2) * 63 = 504,000 sectors.
Then, to reach the 16th surface of the cylinder numbered 400, we need to skip another 16*63 = 1,008 sectors.
Finally, to find the 29 sector, we need to move another 29 sectors.
In total, we moved 504,000 + 1,008 + 29 = 505,037 sectors.
Hence, option C is the answer.
To reach a cylinder numbered n, we need to cross cylinders numbered from 0 to n1.
To reach cylinder numbered 400 (401th cylinder) we need to skip cylinders numbered from 0 to 399, (from cylinder number 0 to 399 there are total 400 cylinders).
Each cylinder consists of 10 plates with 2 recording surfaces and 63 sectors per track.
So total number of tracks to be crossed to reach cylinder numbered 400 = 400 * (10*2) * 63 = 504,000 sectors.
Then, to reach the 16th surface of the cylinder numbered 400, we need to skip another 16*63 = 1,008 sectors.
Finally, to find the 29 sector, we need to move another 29 sectors.
In total, we moved 504,000 + 1,008 + 29 = 505,037 sectors.
Hence, option C is the answer.
Question 52 
〈0, 15, 31〉
 
〈0, 16, 30〉  
〈0, 16, 31〉
 
〈0, 17, 31〉 
Question 52 Explanation:
We know in each track there are 63 sectors. And we know there is one track per surface.
From the given options we can calculate the sector numbers as
Option A  15*63+31 = 976
Option B  16*63+30 = 1038
Option C  16*63+31 = 1039
Option D  17*63+31 = 1102
Hence Option C is the answer.
From the given options we can calculate the sector numbers as
Option A  15*63+31 = 976
Option B  16*63+30 = 1038
Option C  16*63+31 = 1039
Option D  17*63+31 = 1102
Hence Option C is the answer.
Question 53 
expr1 ≡ l(i1, j) + 1  
expr1 ≡ l(i, j1)  
expr2 ≡ max(l(i1, j), l(i, j1))  
expr2 ≡ max(l(i1,j1), l(i,j)) 
Question 53 Explanation:
Question 54 
All elements L should be initialized to 0 for the values of l(i,j) to be properly computed.  
The values of l(i,j) may be computed in a row major order or column major order of L(M,N).  
The values of l(i,j) cannot be computed in either row major order or column major order of L(M,N).
 
L[p,q] needs to be computed before L[r,s] if either p 
Question 54 Explanation:
LCS procedure can followed by either row major or column major order. We can get the same solution by any order. The above question looks very big but they are explaining the procedure of LCS.
Question 55 
Find the names of all suppliers who have supplied a nonblue part.
 
Find the names of all suppliers who have not supplied a nonblue part.  
Find the names of all suppliers who have supplied only blue parts.
 
Find the names of all suppliers who have not supplied only blue parts.

Question 55 Explanation:
If we execute the given query the output will be S3 and S4 i.e., names of all suppliers who didn’t supply blue parts which is option (A).
Option (D) says names of suppliers who didn’t supply only blue parts that means, supplier should supply all other parts for sure and shouldn’t supply blue part.
Question 56 
The schema is in BCNF  
The schema is in 3NF but not in BCNF
 
The schema is in 2NF but not in 3NF  
The schema is not in 2NF 
Question 56 Explanation:
From the given data the FDs will be
(Sid, Street) → Sname
As Sid is a primary key, then
(Sid, Street) will be super key.
Hence, it is in BCNF.
(Sid, Street) → Sname
As Sid is a primary key, then
(Sid, Street) will be super key.
Hence, it is in BCNF.
Question 57 
I = 2  
I = 3  
I = 4
 
I = 5

Question 57 Explanation:
Transmission time (T_{t})=1000/10^{6} seconds =1 ms
Maximum number of frames that can be transmit to maximally pack them is=(T_{t}+2T_{p})/T_{x} = (25+1)/1=26 which is window size
Minimum sequence numbers required = 26
Minimum number of bits required for sequence number is 5.
Maximum number of frames that can be transmit to maximally pack them is=(T_{t}+2T_{p})/T_{x} = (25+1)/1=26 which is window size
Minimum sequence numbers required = 26
Minimum number of bits required for sequence number is 5.
Question 58 
16ms  
18ms  
20ms  
22ms

Question 58 Explanation:
From above diagram we can say that Total RTT will be
1ms (transmitting time for first frame)
+ 25ms (propagation delay from S to R)
+ 1ms (transmitting time for piggybacked ACK)
+ 25ms (propagation delay from R to S)
= 52 ms
Also total time for sender needed to transmit 32 frames (2^{2} = 2^{5} = 32) is 32×1ms = 32ms
So sender has to wait for,
(52  32)ms
= 20ms
Question 59 
{25,12,16,13,10,8,14}  
{25,14,13,16,10,8,12}  
{25,14,16,13,10,8,12}  
{25,14,12,13,10,8,16} 
Question 59 Explanation:
OptionA:
Violating a max heap property.
OptionB:
Violating a max heap property.
OptionC:
Violating a max heap property.
OptionB:
Violating a max heap property.
OptionC:
There are 60 questions to complete.