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[3]-p[1] 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.
See this: http://www.cse.iitd.ernet.in/~soumyadeb/projects/mtp/report/node56.html
and this: http://lasr.cs.ucla.edu/awang/cs111/lecture_2_concurrency.doc

I had marked D :P
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
Interrupt from CPU temperature sensor is non-maskable. All the others are maskable. And, non-maskable interrupts have higher priority than maskable ones.
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
To use your web browser for mail checking HTTP protocol is required
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).
Clearly the answer is B
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

Aptitude answers are
57. D
58. A
59. B
60. C
61. C
62. D
63. C
64. D
65. A

32 comments:

~ThE KiNg~ said...

dude just tell me for q 43.. check it with x=6...
its not a prime but it works...
all i wanna say is it should be other than 1 but either x=y or y=1 that allows z to be equal to x!

and also in question no 55 why n3 will update its N1's cost when it already have the least as 3! ??

~ThE KiNg~ said...
This comment has been removed by the author.
~ThE KiNg~ said...

and brother 1 more thing... 2^n and
n^(logn)

check it with n=2 4 6 8 16....

but wehn u do it with 1024 (2^10)
2^1024=2^(2^10)

but

1024^(log1024)= 2^(10^10)

this exponentiation of n^logn leaves 2^n way behind it....!

the thing to be noticed is that base of log is given as 2!

~ThE KiNg~ said...

ur graph mi8 tell u things different but fella check q 36 with teh value n=2^40...
or n=2^100 ...now i thing it gets clear..

u know dude... in exam it goes like a common person can attempt!

appreciably i like what u did!
graph can be plotted for certain range... and though i am not contradicting u but think on my point.. of that value and any higher value with the power of 2
u will get ma point... and point is valid because.. n^logn is continuous for n>2..
so it will keep dominating 2^n!

they wanna see our tackling limit fella! and i believe i am right on this!

Prab said...

For 43, you confused me. I'll think over it.

For that 2^n and n^logn, I plotted the graph. See the graph again. For upto x=16 n^logn is faster than 2^n. But after that 2^n leaves n^logn way behind it.
I am going to plot another graph with larger values and see what happens. Then I'll post it here.

~ThE KiNg~ said...

why r u plotting it fella...
take any value like in 2 to the power.... whats it...
always take general cases fella!

its working!

Prab said...

See the graph again. See how 2^x leaves x^logx way behind it
http://profile.iiita.ac.in/ISE2010012/files/plot.jpg

~ThE KiNg~ said...

what abt q 55 fella..

its 3 na!

i blv i am ri8! as no one else will have a shorter route to n1 than 3 for n3 n3 cant update it to higher values in a single pass ! hence its should be like that!

Prab said...

Its not a general case. It will work only till x=16.
Ok, check at x=20
2^20=1048576
And
20^log20 on base 2 is 417301 approx

Prab said...

Hope you are now satisfied about 2^n growing faster than n^logn

About 55,
Read in tanebaum the count to infinity problem in distance vector routing and you will understand why it will be 10.
Anyways my 55th is correct but it won't be evaluated because I marked 54th wrong.

Prab said...

Oh, I didn't see ur prev comment about 36 or 100.
At n=32 2^n =2^32
32^log32=32^5=2^25

Hope u get the idea.
At n=256 2^n=2^256
256^log256=256^8=2^64

~ThE KiNg~ said...

u told me to take 20 i am telling u to take n=2^x
then 2^(2^x) . 2^(x^x)

now that ends the discussion dude because

2^n is O(n^n)

now i think us should be satisfied...!

rest is all on but remember what value u will give me to check u will always find a greater next value in power of 2 to challenge u at that point!

take care dude!
best of luck!

Prab said...

I guess you need to brush up some of your concepts related to logarithms and surds.
Best of luck dude!!!
Everything will be clear on 15th march :)

~ThE KiNg~ said...

and fella in q 55 they have related it to 54 simply and as in first round of update 3 will be the cost of route to n1 in n3's table...

no one else will have less than 3 except n2(i.e. 1)
and as it is written in question that change in cost of link is reflected only in the 2 linked node... concept of book is not used.

we r not involving any debugging method in management hence n3 will have; least cost route to n1 as 3 and wont update!

~ThE KiNg~ said...

definitely fella...

and about ma concepts u will ur-self see my brushing up on 15 march!

bbye!
best of luck!

Prab said...

Sure dear :-)

rajdeep said...

Hello, I am expecting around 55 out of 100 in CS . Is there any chance to get into IITs??

Prab said...

@Rajdeep You may get IIT after some good performance in their written test and interviews. Hope for the best :)

@The King
I got where you are wrong. Here is the explanation for that:

put n=2^x

Now n^logn=(2^k)^k=2^(k*k)=2^(k^2)
And 2^n=(2^k)^k

In the first one it will be 2 to the power k*k, not 2 to the power k to the power k, thats where you are going wrong.
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.

ALASKA said...

eh "the king" guy is oversmart huh??? prab let us know his result on 15th march as well , if he shows himself up after that lawl

Prab said...

He won't turn up again :P

anirban said...

what is the answer of Q-44 of binary search tree.Is it B or D .please help

Prab said...

For binary search tree question, the answer is 1

anirban said...

also can you tell me the answer of longest monotonically increasing sequence.I think it uses a dynamic programming .

Prab said...

Yeah right!

Itman said...

Hi thank you for posting 2011 (and 2010!) solutions. Could you, please, explain when in problem 32 (pipelined processor), you all ignore delays between successive stages? Effectively, you say that the next pipeline stage starts before registers are written. Please, note that I am not talking about simple, i.e., sequential mode upon which the pipelined version improves.

On the other hand, from Wikipedia I gather that it might be wrong:
Conventional microprocessors are synchronous circuits that use buffered, synchronous pipelines. In these pipelines, "pipeline registers" are inserted in-between pipeline stages, and are clocked synchronously. The time between each clock signal is set to be greater than the longest delay between pipeline stages, so that when the registers are clocked, the data that is written to them is the final result of the previous stage.

Thank you!

Itman said...

Sorry meant to ask:
Could you, please, explain WHY in problem 32 (pipelined processor), you all ignore delays between successive stages.

Thank you in advance!

Itman said...

PS: maybe in an asynchronous pipeline, when it achieves its maximum throughput, in-between stage register delays, can be ignored. Yet, I am not sure about this. Besides, the problem does not say anything about the type of pipeline. On the other hand, most processors do not use asynchronous pipeline.

Neha Pant said...

the answer of 48th ques is c) 5 acc to me

Prabhakar Kumar said...

@Neha No, its B. Go through it again :)

Prabhakar Kumar said...

@Itman You can go through pipelining topic from a standard text book and think about it. Then you will know

Niharika Gauraha said...

24. A
Is a Wrong Answer, As layer -4 protocol can block entire Http traffic by blocking , port -80..

The answer is D, on a multi-user system it difficult to decide the current user just by analyzing packets headers, needed deep analysis of Data which only application layer can do.

Prabhakar Kumar said...

@Niharika
It's true that you can not decide about the user just by analyzing packet up to any layer.
But a firewall can find out which user is running which processes by querying the OS and then block TCP packets from all processes ran by a particular user between 9PM and 5AM on a certain port.
The answer is A. It can not block HTTP traffic because it can't decide which packet encapsulates an HTTP request.