Gate 2008IT
Question 1 
EXNOR  
implication, negation  
OR, negation  
NAND 
→ NOR and NAND are the functionally complete logic gates, OR, AND, NOT only logic gate can be implemented by using them.
→ And (Implication, Negation) is also functionally complete.
Question 2 
11/12  
10/12  
9/12  
8/12 
P(A') = 1/3; P(A) = 2/3
P(B') = 1/3; P(B) = 2/3
P(A ∪ B) = P(A) +P(B)  P(A ∩ B)
= 2/3 + 2/3  1/2
= 4+43/ 6
= 5/6
= 10/12
Question 3 
2  
3  
4  
5 
→ Chromatic number of a graph is the smallest number of colours needed to colour the vertices so that no two adjacent vertices share the same colour.
Question 4 
5  
4  
3  
2 
(2, 5, 8) is the maximal independent set for a chain of 9 nodes. If we add any start node to the set then it will not be MIS.
Independent set:
A set of vertices is called independent set such that no two vertices in the set are adjacent.
Question 5 
(0 + 1) * 11(0 + 1) *  
0 * 110 *  
0 * 10 * 10 *  
(0 + 1) * 1(0 + 1) * 1 (0 + 1) *

→ 1110 this consists of 3 ones but accepted by given expression. So this is false.
Option B: 0* 110*
→ 0101 this string consists of two is but not accepted by given expression. This is false.
Option C: 0* 10* 10*
→ This is true.
Option D: (0+1)* 1(0+1)* 1(0+1)*
→ 011010  This can have three is but accepted by given expression. So this is also false.
Question 6 
m ≤ 2^{n}  
n ≤ m  
M has one accept state  
m = 2^{n} 
A state in a DFA is a proper suset of states of NFA of corresponding DFA.
→ No. of subsets with n elements = 2^{n}
→ m ≤ 2^{n}
Question 7 
10  
13  
26  
None of these 
Exponent bits  10000011
Exponent can be added with 127 bias in IEEE single precision format then outval exponent
= 10000011  127
= 131  127
= 4
→ In IEEE format, an implied 1 is before mantissa, and hence the outval number is
→ 1.101 × 2^{4} = (11010)_{2} = 26
Question 8 
independent of one variable  
independent of two variables  
independent of three variable  
dependent on all the variables 
Independent of one variable '0'.
Question 10 
A, D, C, E, B  
D, A, C, E, B  
A, C, D, E, B  
A, C, D, B, E 
n^{1/3} < n log^{9} < n^{7/4} < 1.0000001^{n} < e^{n}
Question 11 
If X can be solved in polynomial time, then so can Y  
X is NPcomplete  
X is NPhard  
X is in NP, but not necessarily NPcomplete

That means to be it belongs to NP class, in that class it may be NPcomplete. So, X is NP for sure but may be NPcomplete.
Question 12 
The cost of searching an AVL tree is θ (log n) but that of a binary search tree is O(n)  
The cost of searching an AVL tree is θ (log n) but that of a complete binary tree is θ (n log n)  
The cost of searching a binary search tree is O (log n ) but that of an AVL tree is θ(n)  
The cost of searching an AVL tree is θ (n log n) but that of a binary search tree is O(n) 
Question 13 
Ic, IId, IIIb, IVa  
Ia, IId, IIIc, IVb  
Id, IIc, IIIb, IVa  
Ic, IId, IIIa, IVb

Question 14 
Mathematics Information Technology SAME.  
Mathematics Information Technology.  
Information Technology.  
Information Technology SAME. 
Question 15 
1, 1, 0  
1, 0, 0  
0, 1, 0  
1, 0, 1 
Carry flag = 1
Overflow flag = 0
Sign bit = 0 (MSB bit is 0)
Overflow flag:
In computer processors, the overflow flag is usually a single bit in a system status register used to indicate when an arithmetic overflow has occurred in an operation.
Question 16 
54  
60  
65  
75 
= [(0.9) * 60] + [0.1 * 110]
= 65
Question 17 
True, True  
True, False  
False, True  
False, False 
Question 18 
10,000 bytes  
12,000 bytes  
15,000 bytes  
27,000 bytes 
1 bit for start bit, 8 bits for data, 1 bit for parity, 2 bits for stop bits i.e.,
Question 19 
It is derived from SGML  
It describes content and layout  
It allows user defined tags  
It is restricted only to be used with web browsers

Question 20 
Ia, IId, IIIc, IVb  
Ib, IId, IIIc, IVa  
Ia, IIc, IIId, IVb  
Ib, IIc, IIId, IVa 
(ii) Kazaa and DC++ are P2P applications.
(iii) P2P slip is a processor of PPP.
(iv) DNS allows caching of entries at local server.
Question 21 
[β→(∃x,α(x))]→[∀x,β→α(x)]  
[∃x,β→α(x)]→[β→(∀x,α(x))]  
[(∃x,α(x))→β]→[∀x,α(x)→β]  
[(∀x,α(x))→β]→[∀x,α(x)→β]

L.H.S. : If there is an x such that α(x) is true, then β is true.
R.H.S. : For all x, if α(x) true, then β is true.
Here, the given LHS and RHS are to be same as β is a formula which can be independent of x (if β is true for one x, it is true for every x, and viceversa).
Here, LHS = RHS
So, Option C is valid.
Question 22 
[∃ x, α → (∀y, β → (∃u, ∀ v, y))]  
[∃ x, α → (∀y, β → (∃u, ∀ v, ¬y))]  
[∀ x, ¬α → (∃y, ¬β → (∀u, ∃ v, ¬y))]  
[∃ x, α ʌ (∀y, β ʌ (∃u, ∀ v, ¬y))] 
Question 23 
Question 24 
27  
28  
29  
30 
27/11 = 2
2/11 = 0

29

The exponent of 11 in the prime factorization of 300! = 29
Question 25 
Question 26 
only S1  
S1 and S3  
S2 and S3  
S1 and S2 
As real + real = real and real * real = real
S2: It is closed as rational + rational = rational and rational * rational = rational
S3: It is not closed.
⇒ (0.3+0.4i) + (0.7+0.6i) = 1+i
Both (0.3+0.4i) & (0.7+0.6i) are complex numbers follows S3 but addition of them doesn't follows.
⇒ 1+i, (a^{2}+b^{2}) <= 1
⇒ 1+1 is not less than or equal to 1.
S4: {ia  a ia real}
In this there is no multiplicative identity exists (i.e., 1).
Question 27 
Regular  
Complete  
Hamiltonian  
Euler 
→ In Euler graph all degrees must be even for all nodes. And number of odd degree vertices should be even.
→ So, degree of this new node will be even and as a new edge is formed between this new node and all other nodes of odd degree hence here is not a single node exists with degree odd so this is Euler graph.
Question 28 
(i) and (iv) only  
(ii) and (iii) only  
(iii) only  
(i), (ii) and (iv) only 
(ii) and (iii), not having a least upper bound and greatest upper bound.
Question 29 
S3 and S2  
S1 and S4  
S1 and S3  
S1, S2 and S3 
→ K_{1}R_{1} + K_{2}R_{2} + ... + K_{n}R_{n} = 0
and there is also a linear combination of columns which evaluates to '0' i.e.,
→ K_{1}C_{1} + K_{2}C_{2} + ... + K_{C}R_{n} = 0
Now, any row R_{i} can be written as linear combination of other rows as:
Similar case to columns,
Hence, MX=0, always has one solution i.e., X=0 (which is called trivial solution)
Now if M = 0, then MX = 0 has nontrivial solutions also.
So, S1, S2, S3 are to be true.
Question 30 
2.417  
2.419  
2.423  
2.425 
Question 32 
Set of all strings that do not end with ab  
Set of all strings that begin with either an a or a b  
Set of all strings that do not contain the substring ab  
The set described by the regular expression b*aa*(ba)*b* 
Option B: abab is not accepted by given RE.
Option C: aba is accepted by given RE.
Option D: ab is not accepetd by RE and it belongs to b*aa*(ba)*b*.
Question 33 
L_{1} is not a CFL but L_{2} is  
L_{1} ∩ L_{2} = ∅ and L_{1} is nonregular  
L_{1} ∪ L_{2} is not a CFL but L_{2} is  
There is a 4state PDA that accepts L_{1}, but there is no DPDA that accepts L_{2} 
→ L_{1} ∩ L_{2} = ∅, True and also L1 is nonregular. Option B is true.
→ L_{1} ∪ L_{2} is not a CFL but L_{2} is CFL is closed under union. So option C is false.
→ Both L_{1} and L_{2} accepted by DPDA.
Question 34 
{0^{n} 10^{2n}  n ≥ 1}  
{0^{i} 10^{j} 10^{k}  i, j, k ≥ 0} ∪ {0^{n} 10^{2n}  n ≥ l}  
{0^{i} 10^{j}  i, j ≥ 0} ∪ {0^{n} 10^{2n}  n ≥ l}  
The set of all strings over {0, 1} containing at least two 0’s  
None of the above 
A → 0A  A0  1
B → 0B00  1
In this B → 0B00  1 which generates {0n 102n  n ≥0}
S → AA  B
A → 0A  A0  1
Which generates 0A0A → 00A0A → 00101.
Which is suitable for B and D option. D is not correct because 00 is not generated by the given grammar. So only option B is left. Nonterminal B i s generating the second part of B choice and AA is generating the first part.
{0^{i} 10^{j} 10^{k}  i, j, k ≥ 0} ∪ {0^{n} 10^{2n}  n ≥ 0}
Question 35 
L_{2} and L_{3} only  
L_{1} and L_{2} only  
L_{3} only  
L_{2} only 
L_{1} is limited to fixed range and L_{3} contains even number of 0's which is regular. No need to use more memory to implement L_{3}.
Question 36 
L_{1} = L_{2}  
L_{1} ⊂ L_{2}  
L_{1} ∩ L_{2}‘ = ∅  
L_{1} ∪ L_{2} ≠ L_{1}  
A and C 
L_{2} = (0=1)* 11(0+1)*
Both L_{1} and L_{2} are equal.
Option A is correct.
→ L_{1} ∩ L_{2}‘ = L_{1} ∩ L_{1}‘ = ∅ (option C also correct)
Question 37 
(x⊕y)’ and x’⊕y’  
(x⊕y)’ and x⊕y  
x⊕y and (x⊕y)’  
x⊕y and x⊕y 
Excitation table of JK:
Question 38 
Assume that EA = (X)+ is the effective address equal to the contents of location X, with X incremented by one word length after the effective address is calculated; EA = −(X) is the effective address equal to the contents of location X, with X decremented by one word length before the effective address is calculated; EA = (X)− is the effective address equal to the contents of location X, with X decremented by one word length after the effective address is calculated. The format of the instruction is (opcode, source, destination), which means (destination ← source op destination). Using X as a stack pointer, which of the following instructions can pop the top two elements from the stack, perform the addition operation and push the result back to the stack.
ADD (X)−, (X)  
ADD (X), (X)−  
ADD −(X), (X)+  
ADD −(X), (X)+ 
Lets say SP is 1000 initially then after it calculates the EA of source (which is 1000 as it decrements after the EA). The destination becomes 998 and this is where we want to store the result as stack is decrementing.
In case of C and D it becomes,
998 ← 998 + 998
Question 39 
Consider a CPU where all the instructions require 7 clock cycles to complete execution. There are 140 instructions in the instruction set. It is found that 125 control signals are needed to be generated by the control unit. While designing the horizontal microprogrammed control unit, single address field format is used for branch control logic. What is the minimum size of the control word and control address register?
125, 7  
125, 10  
135, 7  
135, 10 
⇒ 2^{m} ≥ 980
⇒ m ≥ 10
⇒ 10+125 bits and 10 bits
⇒ 135, 10 bits
Question 40 
A non pipelined single cycle processor operating at 100 MHz is converted into a synchronous pipelined processor with five stages requiring 2.5 nsec, 1.5 nsec, 2 nsec, 1.5 nsec and 2.5 nsec, respectively. The delay of the latches is 0.5 nsec. The speedup of the pipeline processor for a large number of instructions is
4.5  
4.0  
3.33  
3.0 
For pipelined system = Max(stage delay) + Max(latch delay) = 2.5 + 0.5 = 3.0
Speedup = Time in nonpipelined system/Time in pipelined system = 10/3 = 3.33
Question 41 
6 and 1, 2, 3, 4  
7 and 1, 2, 4, 5  
8 and 1, 2, 4, 5  
9 and 1, 2, 3, 5 
(Each page contains 16 bytes, so say for page0, it contains the virtual address 015)
0: page fault1, pages in memory0
4: page fault1, pages in memory0
8: page fault1, pages in memory0
20: page faults2, pages in memory0,1
24: page faults2, pages in memory0,1
36: page faults3, pages in memory0,1,2
44: page faults3, pages in memory0,1,2
12: page faults3, pages in memory1,2,0
68: page faults4, pages in memory1,2,0,4
72: page faults4, pages in memory1,2,0,4
80: page faults5, pages in memory2,0,4,5
84: page faults5, pages in memory2,0,4,5
28: page faults6, pages in memory0,4,5,1
32: page faults7, pages in memory4,5,1,2
88: page faults7, pages in memory4,1,2,5
92: page faults7, pages in memory4,1,2,5
Question 42 
6  
8  
10  
12 
First evaluate 2's complement of given numbers, if numberis negative then append 0 into LSB.
Then each pair from LSB to MSB (add 1 bit at a time):
00 = 0, 01 = +1, 10 = 1, 11 = 0
Booth's algorithm based on multiplier which is already given in binary representation:
0111 0111 1011 1101
= Now, append 0 into LSB of
(0111 0111 1011 1101) = 0111 0111 1011 1101 0
Now, Booth's code (add 1 bit at a time, from LSB to MSB):
= 01, 11, 11, 10, 01, 11, 11, 11, 10, 01, 11, 11, 11, 10, 01, 10
= +1 0 0 1 +1 0 0 0 1 +1 0 0 0 1 +1 1
Here, 4 substractions and 4 additions required,
Total = 8
Question 43 
Θ(n)  
Θ(kn)  
Θ(nlogn)  
Θ(n^{2}) 
Question 45 
(a, b), (d, f), (f, c), (g, i), (d, a), (g, h), (c, e), (f, h)  
(c, e), (c, f), (f, d), (d, a), (a, b), (g, h), (h, f), (g, i)  
(d, f), (f, c), (d, a), (a, b), (c, e), (f, h), (g, h), (g, i)  
(h, g), (g, i), (h, f), (f, c), (f, d), (d, a), (a, b), (c, e)

(A) (d, f) is chosen but neither 'd' nor 'f' vertices are part of previous MST (MST made till previous step).
(B) (g, h) is chosen but neither g or h vertices are part of MST made till previous step.
(C) Correct.
(D) (f, c) is chosen, but at that point (f, d) had less weight. So, (f , d) should have been chosen.
Question 46 
I and II are preorder and inorder sequences, respectively  
I and III are preorder and postorder sequences, respectively  
II is the inorder sequence, but nothing more can be said about the other two sequences  
II and III are the preorder and inorder sequences, respectively

So, out of the given sequence only I & II are having such kind of order, i.e., K at the beginning and at the last.
Therefore, II is the preorder and I is postorder and the sequence III will definitely be inorder.
Question 47 
I and III only  
II and III only  
II, III and IV only  
I, II and III only

IV) After visiting 'c', 'e' or 'f' should be visited next. So, the traversal is incorrect.
Question 49 
dlrow  
Null String  
dlrld  
worow

Question 50 
5, 5  
5, 4  
4, 5  
4, 4 
{Swap3 (&num1, &num2) ; }"
Statement is true, so call by reference will be performed and the value of num1 and num2 will get exchanged.
Question 51 
2, 3  
2, 4  
3, 2  
3, 3 
First for loop will run for i = 0, 2 and 4 as i is incremented twice and resultant array will be 'a' = 2, 2, 4, 4, 5, 6, 7, 8. Loop will terminate at i = 4.
After that value of 'i' will become '3' as there is a decrement operation after for loop.
Next for loop is running for j = 7, 6, 5 and corresponding 'i' values which is a local variable inside for loop will be
3(7/2), 3(6/2), 2(5/2)
Array after this for loop will be
a = 2, 2, 3, 2, 5, 6, 2, 8.
After the loop, current 'i' value is 3 and elements at a[3] = 2.
Question 52 
*(p+2) = a[0][1] = b
*(p+4) = a[0][2] = c
*(p+1) = a[1][0] = d
*(p+3) = a[1][1] = e
*(p+5) = a[1][2] = f
Question 53 
The process can deadlock  
One of the threads can starve  
Some of the items produced by the producer may be lost  
Values generated and stored in ‘x’ by the producer will always be consumed before the producer can generate a new value 
(B) No starvation happen because there is alteration between Producer and Consumer.
(C) No items is lost.
Question 54 
Both starvation and deadlock can occur  
Starvation can occur but deadlock cannot occur  
Starvation cannot occur but deadlock can occur  
Neither starvation nor deadlock can occur

Now, maybe the process has not used the resources it released yet. This may happen again when the process requests another resource.
So, the process starved for proper utilization of resources.
Deadlock will not occur as it is one of the deadlock prevention scheme.
Question 55 
degenerate to shortest job first  
degenerate to priority scheduling  
degenerate to first come first serve  
none of the above 
Question 56 
Id, IIa, IIIb, IVc  
Ib, IIc, IIIa, IVd  
Ic, IId, IIIa, IVb  
Ib, IIc, IIId, IVa 
The bit indicates that its associated block of memory has been modified and has not been saved to storage yet. Dirty bits are used by the CPU cache and in the page replacement algorithms of an operating system.
R/W bit:
If the bit is set, the page is read/ write. Otherwise when it is not set, the page is read only.
Reference bit:
Reference bit is used in a version of FIFO called second chance policy, in order to avoid replacement of heavily used page.
Valid bit:
Valid bit is not used for page replacement. It is not used in any page replacement policy. It tells the page in the memory is valid or not. If it is valid it is directly used and if it is not then a fresh page is loaded. So, basically it is page initialization, because we are not replacing, it is initializing, we not knocking out somebody, we are filling empty space. So initialization and so option (D).
Question 61 
gives a lossless join, and is dependency preserving  
gives a lossless join, but is not dependency preserving  
does not give a lossless join, but is dependency preserving  
does not give a lossless join and is not dependency preserving

(A, B, C) (B, D)  common attributes is B and B→D is a FD (via B→C, C→D), and hence, B is a key for (B, D). So, decomposition of (A, B, C, D) into (A, B, C) (B, D) is lossless.
Thus the given decomposition is lossless.
The given decomposition is also dependency preserving as the dependencies A→B is present in (A, B), B→C is present in (B, C), D→B is present in (B, D) and C→D is indirectly present via C→B in (B, C) and B→D in (B, D).
Question 62 
in BCNF  
in 3NF, but not in BCNF  
in 2NF, but not in 3NF  
not in 2NF 
Since there is a partial dependency B→G.
So the relational schema R is Not in 2NF.
Question 63 
S1, S2 and S3 are all conflict equivalent to each other  
No two of S1, S2 and S3 are conflict equivalent to each other  
S2 is conflict equivalent to S3, but not to S1  
S1 is conflict equivalent to S2, but not to S3 
For S1:
For S2:
For S3:
Hence, S1 is conflict equivalent to S2, but not to S3.
Question 64 
A 1Mbps satellite link connects two ground stations. The altitude of the satellite is 36,504 km and speed of the signal is 3 × 10^{8} m/s. What should be the packet size for a channel utilization of 25% for a satellite link using goback127 sliding window protocol? Assume that the acknowledgment packets are negligible in size and that there are no errors during communication.
120 bytes  
60 bytes  
240 bytes  
90 bytes 
RTT = 4×Time to reach satellite (S1→S, S→S2, S2→S, S→S1)
∴ RTT = 0.48
Question 65 
125 bytes  
250 bytes  
500 bytes  
None of these 
So,
Question 66 
1  
2  
3  
4 
Here, we need to change minimum 3bits, and by doing it we get correct parity column wise and row wise (correction marked by boxed number).
Question 67 
S1, S2 and S4 only  
S1, S3 and S4 only  
S2 and S3 only  
S1 and S4 only 
→ In LSR shortest path is calculated at each every router. (B) is wrong.
→ In DVR also shortest path is calculated at each and every router. (C) is wrong.
→ Since DVR is based upon local knowledge whereas LSR is based upon global knowledge.
Question 68 
S1, S2 and S3 only  
S1 and S3 only  
S3 and S4 only  
S1, S3 and S4 only 
TCP handles both congestion and flow control ⇒ True.
S2:
UDP handles congestion but not flow control ⇒ False, because UDP neither handles congestion control nor flow control.
S3:
Fast retransmits deals with congestion but not flow control ⇒ True.
S4:
Slow start mechanism deals with both congestion and flow control ⇒ False, because it has nothing to do with flow control. Flow control is taken care by Advertisement window.
Question 69 
S2 and S3 only  
S1 and S4  
S1 and S3  
S2 and S4 
S2 → False, because if after ACK client immediately sends data then everything goes on without worry.
S3 → False.
S4 → True.
Question 70 
^{n}C_{2} = n(n1)/2
In case of public key, each sender has its own public key as well as private key. So, no. of keys are 2n.
Question 71 
II and III only  
I and III only  
III and IV only  
III only 
Question 72 
I, II and IV are inorder sequences of three different BSTs  
I is a preorder sequence of some BST with 439 as the root  
II is an inorder sequence of some BST where 121 is the root and 52 is a leaf  
IV is a postorder sequence of some BST with 149 as the root

B) False because if 439 is root then it should be first element in preorder.
C) This is correct.
D) False because if 149 is root, then it should be last element in postorder.
Question 74 
for each school with more than 200 students appearing in exams, the name of the school and the number of 100s scored by its students  
for each school with more than 200 students in it, the name of the school and the number of 100s scored by its students  
for each school with more than 200 students in it, the name of the school and the number of its students scoring 100 in at least one exam  
nothing; the query has a syntax error

Question 75 
The empty set  
schools with more than 35% of its students enrolled in some exam or the other  
schools with a pass percentage above 35% over all exams taken together  
schools with a pass percentage above 35% over each exam 
{ x  x ∈ Enrolment ∧ x . schoolid = t }  * 100 > 35 }
This is school with enrollment % is 35 or above.
Question 76 
n_{1} = 3
n_{2} = 1
n_{3} = 1
So, option (B) satisfies.
Question 77 
2 * n_{1} – 3  
n_{2} + 2 * n_{1} – 2  
n_{3} – n_{2}  
n_{2} + n_{1} – 2 
n_{1} = 3
n_{3} = 1
So, option (A) satisfies.
Question 78 
aabbaba  
aabaaba  
abababb  
aabbaab 
S→aA
S→aaAb
S→aabAab
S→aabbAaab
S→aabbaab
Question 79 
6 and 1  
6 and 2  
7 and 2  
4 and 2 
S→aA
S→aaAb
S→aabAab
S→aabbAaab
S→aabbaab
⇒ 6 steps are required
Only 1 parse tree is there.
Question 81 
000011000  
110001111  
00011000  
110010101 
So lets first convert given Hexadecimal no. into binary number,
Question 82 
010110101  
010101101  
10110101  
10101101 
So, after traversing the tree we get:
10101101
Question 83 
Both P1 and P2  
P2 only  
P1 only  
Neither P1 nor P2 
But P2 prints the reverse of original sequence printed by original program.
Question 84 
1  
2  
3  
6 
XX.XX.XX.96, XX.XX.XX.64 and XX.XX.XX.128.
Question 85 
192.168.1.67  
192.168.1.110  
192.168.1.135  
192.168.1.155 
Subnet no. of host X is,
Now, the gateway must also have the same subnet number.
Let's take IP 192.168.1.110 of R1,
and hence this can be used by X.