## Monday, February 14, 2011

### GATE 2011 CS Solutions

Last year I had released the solutions for GATE2010 with explanation. This time I am releasing the same for GATE2011.
Disclaimer: I don't guarantee that my solutions are hundred percent correct, because I am also a student like you and far from perfection. If you think that any explanation given for a particular problem is wrong, then comment with your own version of explanation. If found correct, I'll edit mine and put yours.

If you are just preparing for GATE, you should solve more and more questions. And for that I would recommend GKP Publisher's Question Bank. Although there are some mistakes in the book for solutions to some problems, but I recommend this book solely for the huge collection of problems it has.

My answer booklet was D. So to find which question numbers given here map to which ones in yours, you may download my question paper booklet's copy.

Now lets start:

1. C
Because regular languages are closed under Complementation. Sigma star minus P means the complement of P, which is a regular language.
2. A
I am still confused about this. I won't say anything. You can find it in Cormen's algorithm book. There is a topic on Longest Common Subsequence.
3. B
Although A and B both look like heap but read page 127 in Cormen. A heap is almost a complete binary tree which is filled on all levels. In A, the 2nd level is not filled completely i.e. 8 should have a right child.
4. C
Lets consider base memory address of array C is 1000. So, p+p-p means p+(E-A) = p+4 which is on 2. So %s will print everything from 2 to the nearest null terminator i.e. '\0' hence 2011 will be printed.
5. D
Page 277, point 7 in Arnold S. Berger's book of Hardware and Computer Organization
6. B
In 10^6 memory accessed time required = 20ns*10^6 + 10ms = 30ms
So in 1 memory access (30*(10)^-6)ns which is 30ns.
7. A
Lexical analysis is done with regular expressions. So FSA is the answer.
8. C
See here http://en.wikipedia.org/wiki/Variance
Standard deviation is SQRT(Variance). Variance is always greater than equal to zero.
9. B
Both are planar because both can be drawn without any edges intersecting any other. See the diagram:

10. C
See the figure on page 128 in Galvin's latest edition.

Most people are saying A or B which is wrong.
and this: http://lasr.cs.ucla.edu/awang/cs111/lecture_2_concurrency.doc

11. A
ceil(log258 on base 2) i.e. 9
12. B
Solve it directly:
(P+Q'+R')(P+Q'+R)(P+Q+R')
=(P.P+P.Q'+PR+PQ'+Q'+Q'R+PR'+Q'R'+R'R)(P+Q+R')
=(P+P(1+Q'+R+Q'+R')+Q'(1+R+R'+0))(P+Q+R')
=(P+Q')(P+Q+R')
=P+PQ+PR'+PQ'+Q'Q+Q'R'
=P(1+Q+R'+Q')+0+Q'R'
=P+Q'R'
13. A
because two account numbers of different banks may be same
D is wrong because if S is a superkey then S union anything will be a superkey
14. D
Put X and Y as inputs and get the equation. For A, B and C it is X'Y'+XY which is the formula of EX-NOR gate.
15. D
16. D
SRS MUST not have any kind of algorithms of HOW to implement. It contains details about WHAT to implement.
17. D
To display client time you need to do JavaScript. Pure HTML can't do. Page refreshing can be done by <meta http-equiv=refresh.............. For embedding there is a dedicated tag <embed> in html. For reloading, <meta> tag can be used.
18. B
Its a fact, and I don't need to put any explanaton for it :P
19. I didn't mark it. Didn't know the formula.
20. C
For switching to Kernel mode only the mode bit needs to be toggled. For switching process, context-switch is needed which involves lot of work. So t1<t2
21. I didn't touch this question
22. C
To send a mail from a mail client to mail server you need SMTP.
To check and download mail from a mail server you need POP or IMAP
23. A
1/3 is pretty easy. But I marked 2/3 because my probability is too weak and I did some wrong calculation.
24. A
A Layer 4 firewall can't block HTTP traffic because it can inspect packets upto transport layer only. HTTP isn't in the jurisdiction of layer 4 firewall. For blocking HTTP traffic, deep packet inspection firewalls are required.
25. C
Keywords are recognized during lexical analysis which is done using regular expressions and DFAs/NFAs
26. C
I marked A but that will be true if in 2nd column 1st and 3rd rows are not both Sunderajan.
27. A
Case (i) – When co-efficient is zero – T1, T2
Case (ii) – When D is positive – T2, T5
Case (iii) – When D is zero – T1, T3, T4
Case (iv) – When D is negative – T6
Option A is the correct non-redundant set.
28. A
Derive regular expressions and match
29. B
6000rpm=100rps
1 rotation in 1/100 seconds i.e. 10ms
so half a rotation in 5ms which is the average seek time
Now total time required for 100 libraries=100*(10+5)=1500ms=1.50ms
30. D
32 byte cache block size=2^5 i.e. 5 bits for block offset
No. of blocks in cache=8KB/32byte=(2^3*2^10)/2^5=2^88 i.e. 8 bits for index
Tag information=tag for memory+1 valid+1 modified=(32-8-5)+1+1=21
For 256 blocks, 256*21=5376 bits of tag info will be maintained.
Some people said 256*19 because valid and modified bit are part of tag in the question. Read the question carefully. They are part of tag information maintained by cache controller. They are not the part of tag itself. If you use only 17 bits for tag then this architecture will be faulty and you won't be able to correctly identify memory block.
See here:
http://hpc.serc.iisc.ernet.in/~govind/hpc/L14-Cache.txt
Scroll down to the part where it is clearly mentioned:
Thus along with the data in the cache for every cache block,
it is required to store the tag filed (to identify the memory
block), valid field (to indicate if the data in the cache
block and tag fields are valid or not), and possibly a
dirty bit (to indicate if the cache block has been modified
or not). Thus for each cache block, we have a dirty bit ,
valid bit and tag
31. I didn't touch
32. B
I marked D which is wrong.
Correct way to solve is:
Let us consider number of instructions is 1000
Speedup=(1000*30)/(1000-1+4)*(11+1)
i.e. N*T/(N-1+S)*(L+D)
where N is number of instructions
T is total time of all stages in non-pipelined
S is no. of stages in pipeline
L is time taken by longest stage in pipeline
D is mean delay between stages
33. A
In case of lower triangular matrix the diagonal elements are the eigen values.
34. C
See here in page 14
myweb.lmu.edu/dondi/share/db/indexing-and-hashing.pdf
35. C
Here you may read how to do it with pen and paper:
http://en.wikipedia.org/wiki/Matrix_chain_multiplication
(M1*(M2*M3)*M4) gives 100*20*5+10*100*5+10*5*80=10000+5000+4000=19000
36. A
n^(3/2) and nlogn are directly out of the competition. The real competition is between 2^n and n^logn. See the graph below that I plotted with GNUPLOT to see yourself which one wins.
Put n=2^k
Now n^logn=(2^k)^k=2^(k*k)=2^(k^2)
And 2^n=2^(2^k)
In the first one it will be 2 to the power k*k, not 2 to the power k to the power k
In the second one it will be 2 to the power(2 to the power k)
Find me any value of n greater than 16 for which 2^n is lesser than n to the power logn.
I bet you can't find.
See this:
At n=20
2^n=1048576 and n^logn=417301 approx
At n=32
2^n =2^32 and 32^log32=32^5=2^25
At n=256
2^n=2^256 and 256^log256=256^8=2^64

37. A
a-b can be done with one register.
Take a in accumulator. Subtract b from it and keep the result in accumulator itself. So you just need on accumulator, no other register.
Next, take c in an accumulator and add d to it and store it in the accumulator. Now subtract the contents of accumulator from e and store in the accumulator itself.
Now add the contents of both the accumulators and store it in any one of them.
So we need just two accumulators for the whole operation. So, 2 registers is the correct answer.
38. A
Make a gantt chart and you will have 0+(5-1) for P0, 0 for P1 and (13-2) for P2 i.e. 15ms. Average waiting time will be 15/3=5ms

39 and 40. I didn't touch this as probability and statistics is not my cup of tea
41. A
Here is the pattern:
X Y
_ _
1 1
2 3
3 7
4 15
5 31
6 63
7 127

42. I didn't solve
43. A
Just apply some logic and you will get the answer
A(x)=x is not 1
B(x)=for all y ((there exists z such that x=y*z )implies(either y=x or y=1))

A(x) and B(x) give x as prime
44. D
I marked B but it is D.
45. A
In non-DMA total time=1+1+500(2+2+1+1+1)=3502
In DMA total time=20+(500*2)=1020
Speedup=3502/1020=3.43~3.4
46. C
Clearly L3 is not context free
47. B
Consider up arrow as * and down arrow as +
So according to the associativity mentioned, the equation will be (7+(3*(4*3))+2).
48 & 49 will be B & D respectively
See my solution below

50. D
Follow the recursion and you will get 1+0+0+0+0+1
51. B
Follow the recursion and you will get 5+4+3
52. B
Draw a 5 node graph according to the specs given. Find MST by Kruskal's algo. Only B satisfies the MST.
See the below image

53. C
Draw a 10 node graph according to the specs. Find MST. Find the distance between v5 to v6. It is 31. See the below diagram

54. I marked D and it is wrong
55. C
It is intuitively 10