## Wednesday, February 17, 2010

### GATE 2010 CS Solutions

Gateforum announced that they will release solutions by 7:30PM on Feb15th, but they didn't. None other coaching institute did. All of them released answer keys only and slept, keeping the students in confusion.
So, I decided, I will post the solutions to selected questions.

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.

Disclaimer: These are my developed solutions. I am a student and I can't guarantee the correctness of the solutions. And yeah, don't think that I solved them all correct. I am not a computer scince wizard either.

Note: Click on the images to enlarge.

First, get the question paper here or here(Thanks Sapan for the second version!)

Now, lets start!

Q-1: I fiddled with it and got the correct answer but didn't mark it cuz of fear of getting it wrong!

Q-2, 3,4,5 I skipped because I had skipped large amount of discrete maths portion and I'm not comfortable with serious topics.

Q-6:
The rightmost thing appearing in this image is P. Read it as PR'. I stripped the R' by mistake while cropping, and overwrote the image.

Q-7:
I hit B as explained below.
The refresh operation in a DRAM chip cycles through each row reading the contents of each cell in the row and writing them back.
For the given problem our RAM module will have 32 chips. Pretty easy calculation i.e. (4M*8bits)/(1M*8bits). One refresh cycle refreshes 1 row of each chip being used to construct the module. Thus we require 1K refresh cycles to refresh the wole module by refreshing 1 row of each chip in the module at once.
Hence time required will be 100*(2^10)ns

Q-8:
F 8 7 B is
1111 1000 0111 1011
Multiplying by 8 means multiplying by 2, three times successively. That accounts for 3, 1-bit left shifts i.e. 3-bit left shift.
On performing 3-bit left shift on the number we get
1100 0011 1101 1000
Thats C 3 D 8

Q-9:
Using the equation of multiplexer we have
f=RP'Q'+R'P'Q+R'PQ'+RPQ
=P'(Q'R+R'Q)+P(R'Q'+RQ)
=P'(Q XOR R)+P(Q XNOR R)........(since, A'B+AB' is A XOR B and AB+A'B' is A XNOR B)
=P'(Q XOR R)+P(Q XOR R)'
=P XOR (Q XOR R)
=P XOR Q XOR R..................(since, XOR is associative)

Q-10: I fiddled with it for quite some time and hit C. I believe I was wrong.

Q-11:
I marked B due to some misunderstanding and being in a hurry(dunno why?)!
Proceed to the function call. We have the address of i in p and address of j in q. Now the operation p=q; will transfer j's address in p. The second operation *p=2; will put 2 at j's address. i's address will remain untouched. Hence after returning from the function we get 0 2 as output from the printf function.

Q-12:
I hit D cuz of a calculation mistake.

Q-13B 14C 15D

Q-16: Seems to be an ambiguous question. A and D are the contenders for being the answer. I hit A.

Q-17:

Q-18:
Each node except root in a B+ Tree can hold between T-1 and 2T-1 keys where T is the order of the tree.
In the problem, we have
2T-1=5
=>2T=6
=>T=3
So the min. i.e. T-1 will be
=>T-1=2 hence option B

Q-19 C. Thats pretty obvious

Q-20: I hit A. But thats wrong. 2PL doesn't guarantee freedom from deadlocks. Timestamp ordering does. So B is the right answer.

Q-21: I hit D. I don't have any explanation for it. I had skipped this portion while studying Software Engineering.

Q-22: B is pretty obvious

Q-23: I skipped. I am not comfortable with this thing.

Q-24: 196 is the obvious answer. No need to explain.

Q-25: I hit B but thats wrong. D will be correct. Read Galvin's book.

Q-26: I skipped. I'm not comfortable with probability.

Q-27: Same as above.

Q-28: I drew some example graphs and guessed the answer to be D. And I got it correct!!!!

Q-29: D

Q-30: B
For all x, there exists y, there exists t, not F(x,y,t)
For every person x out there, there is a person y, and a time t such that x can't fool y at time t.
Option B i.e. No one can fool everyone all the time expresses the meaning best.

Q-31:
A is correct. This is a simple problem involving De Morgan's law. No need to explain.

Q-32: I skipped. No idea. I ain't an electronics wizard.

Q-33: B

Q-34:
I took an example sequence and hit A after applying some unexplainable heuristics. :P

Q-35:
Just follow the recursive call, you'll get 12+(7-(13-(4+(11-(6))))) which is 15.

Q-36:
D is the obvious answer. Moving the last element to the first means setting the pointer of second last element to null and setting head to point to the value of last element(now first) and setting its next pointer point to the to the previous first node.

Q-37:
d=a+b(requires 3 registers. 2 for operands, 1 for result)
e=c+d(a is not used as an operand anywhere ahead so we can overwrite it as e. so, still 3 registers)
f=c+e(we don't need d as an operand, so overwrite it as f. still 3 registers)
b=c+e(we don't need c as operand, so overwrite it as b. still 3 registers)
e=b+f(we don't need b as operand, so overwrite it as e. still 3 of them)
d=5+e(we can overwrite e with the new d. still 3)
return d+f
We're done with 3 registers. But I marked 4 registers. Because in the middle of this whole evaluation I toppled on a variable and needed an extra one.

Q-38: I am uncomfortable with compiler design. I skipped.

Q-39: This one seems to be ambiguous. Consider the string 1010011. It has even number of ones. But none of the given regular expressions can generate it. I didn't mark anything.

Q-40: A CFG can keep the count of 1 thing. D seems to be the obvious answer. I hit C. Even I don't know why!!!!

Q-41: I hit B because I thought, to accept a substring we need equal or lesser number of states. Dunno whether I am write or wrong, but everyone says I am wrong. Rest in peace.

Q-42:
I hit C cuz of a confusion. *damn*

Q-43:

Q-44:
Go through the test conditions T1 through T4.
You'll deduce that:
T1->S1
T2->S3
T3->S1
T4->S2,S4

so T1,T2,T4->{S1.S2,S3,S4)

Q-45 and 46 I skipped because I am scared of these things.

Q-47: D is the obvious answer. No need to explain. Just bitwise AND 255.255.255.224 to 10.105.1.113 and 10.105.1.91 and you will get different network addresses.

Q-48 and 49:

Q-50 and 51:
Label the rows and columns of the matrix as 0,1,2,3,4 and draw the graph. Apply Kruskal's algorithm on Q-50 skipping the second 1 weight edge.

Edit: For Q-51 the required path is 1-0-4-2 and that is 8 units.. I made the same mistake(rather blunder) in exam hall as well which will set me back by -2.66 marks andaround 150-250 rank positions.

Q-52: Pretty easy. Ans. C

Q-53: I made some heuristics and guessed the ans. to be C 30. And that seems to be right! Al the coaching institutes converge at that answer!

Q-54 and 55: I think I got both of them wrong. I hit B and D respectively.

Bangalore Properties Review said...

for the Q no. 48 and 49....if we transfer a block from L2 cache to L1 cache then it needs 4 cycles. that means 4 times to read L2 and 4times to write in L1.

Based on this the answer of 48 will be 22*4=88 and answer of 49 will be 200*4+20*4+88=968 ms

REY said...

:cheers

prab97 said...

@Raja Thats a disputed question. Check out the related post on gatementor. 902 and 968 are the obvious answers. I'm in the team that believes 902 is the answer!

prab97 said...

:grin@REY Mysterio

ganesh said...

In question no.51 you have clearly missed the right answer:
1-0-4-2 gives you 8

prab97 said...

Yeah, gani u r right! I realise my blunder now! So, another minus 2.66 for me. :damn I'm ruined!

Unknown said...

For Q51) Weight(1-0-4-2) = 1+4+3 = 8

freaky_ss said...

i guess for 54=>c and for 55=>b

freaky_ss said...

hey prabhakar...r u sure for
18=>b
30=>b

i m in a big fix.....
plz help me out!!!

54 and 55 k ans bhi bata do !!

freaky_ss said...

http://forum.gatecounsellor.com/viewtopic.php?f=108&t=62no

prab97 said...

@sujit Yeah, u r right.

@freaky_ss Yeah, I am sure about 18-B and 30-B. For 54 and 55, the correct aswer is C and B respectively.

freaky_ss said...

yuppy !!!! :)

freaky_ss said...

hey !!@prab...hw can u say that made easy ans r worst...when most of yurs and its ans match??

prab97 said...

Well, thats because they have given wrong answers to some very simplest of the questions in the aptitude section like 65, 61, 56.
Later I saw, they have given most correct answers in the CS section i.e. 1-55. But I realized that after I posted criticism for them. LOL

By the way, around how much are you getting according to them?

freaky_ss said...

i m getting 44.7 according to MADE EASY....i hav nt attempted 65th question ..bt i think made easy is correct...
65=>b
61=>c(this is 100 %)
56=>b(i ticked A...made easy is banking on C...bs yahi ans galat hai unka sayad)......

63 ka option kya hai according to u???

i ticked D

freaky_ss said...

k...now i got u...i guess u hav older keys of made easy....it has put recheckd keys on its site...

freaky_ss said...

according to me GATE FORUM ans r d worst...

prab97 said...

Oh god! I didn't know they put an updated key!!! lol I sould recheck now with the latest key.

A/C to me
65:B
61:C
56:B

Old keys of made easy say 65:D, 61:A

Yeah, u r right with 56:B I hit A and I know I am wrong.

I ticked 63:A

I'm getting 42.66. Lets see what happens on 15th March. Sach ka saamna usee din hoga!!! I'm damn scared!

Yup, I agree. Gateforum keys are the worst.

prab97 said...

What did u hit in 48 and 49??? What do you think should the answer be? I marked 22 and 902. Made Easy says 88 and 968. There is a big debate about it on gatementor in a post. Some advocating the 22-902 duo and others the 88-968.

freaky_ss said...

i didnt attempt q48 n 49...

prab97 said...

oh ok...

freaky_ss said...

@prab if possible....q 54 n 55 k ans bata do along with solns

freaky_ss said...

wht is yur result in GATE2010?

prab97 said...

I got AIR1504, Marks 42.33, GATE Score 614.
My roll no.: 3095251

freaky_ss said...

I got AIR 1649, Marks 41.67, GATE Score 605.
My roll no.: 3099429

@prab do we have any chance??? agar kucch pata chale to kindly discuss.....

prab97 said...

We can try for IIT Roorkee. Also, M.S. in IITD. And M.Tech in IITB under RA category.

arunesh srivastava said...

hey...u r solutions were almost right can u tell me that which college u get..
and can u also tell me that how to prepare for gate imean the books,shedule etc...

prab97 said...

Hi Arunesh! You seem to be a GATE 2011 aspirant. All the best! I'll post in my blog all kind of help that I can for the latest GATE aspirants. All the links to resources and articles on GATECS preparation will be posted soon. But Now a days I am busy with admission helter-skelter. Lets see which college I get. I'm trying for 4 IITs but the chances are very lean. As a backup I have chosen IIIT Bangalore.

arunesh srivastava said...

yeah i'm a 2011 aspirant but i scora only 12 no.s in 2010..as i'm not prepared well...
best of luck to u.......

Ruman said...

hi prabhakar
i m in cs 3rd year....i appeared in gate 2010...my gate score is 605 with a rank of 1649....wich is close 2 urs....so pls tell d cutoffs in d various IITs nd where u r getting admission...also wat shud b a safe rank for IITB....i plan to appear again next year....so any help regarding preparation...

prab97 said...

@living_mystery Getting a rank within 110 will guarantee you a seat in IIT Bombay. I've applied in 4 IITs and 2 IIITs. The interview season hasn't yet started. I'll post in the blog as I appear in the interviews.

Ruman said...

hey thnx prabhakar 4 ur rply....shud i join any coaching institute like gateforum or shud i prepare on my own....also hw shud i prepare....any tips

prab97 said...

Joining classroom coaching is not much needed, but join the Gateforum test series. Although the questions they ask aren't upto the mark, but it will be very beneficial for you since it will expose those areas from the syllabus you aren't good at so u can polish the areas :)

Ruman said...

prab97 said...

I don't think that the quality of material they provide in correspondence course is good.
Use your B.Tech text books for the prearation. And get the previous year GATE questions

Ruman said...

thnx dude....thn i'll join the test series only....nd prepare on my own...for my b.tech. i m following these books :
OS - galvin
DBMS - Korth+Navathe
Algorithms - Sahani
Network - Forouzan
S/w Engg - Rajib Mall
Automata - Mishra & Chandrasekharan
Organization - M.Mano
C & C++ - Schildt
DS - Sahni
Digital - Salivahanan
cn u suggest some better books?

prab97 said...

DBMS-Only Navathe is enough. No need of Korth.
Networks-Tanebaum is preferred by GATE question setters
S/W Engg.-Pressman is used for setting questions
Automata-opcroft and Ullman is the standard book
Comp. Org.-Morris Mano is Ok. But for numerical problems related to cache memory, you also have to follow Patterson. For pipelining and caches and some other important topics, also use the resources available on IISc site here http://hpc.serc.iisc.ernet.in/~govind/hpc/

C++ is not in syllabus. For C, Let Us C from Yashvant Kanitkar is perfect.

Data Structures and Discrete Mathematics- Seymour Lipschutz

Digital Logic- Morris Mano

These are all the most standard books. Most of the GATE questions are set from these books only. The tiniest points are captured by setters and then asked.

Ruman said...

thnx dude...wat bout maths??....

prab97 said...

For Discrete Maths u have Seymour Lipschutz.
I skipped large parts of Maths syllabus during preparation, that was because I never actually practiced maths in past 4 years!!! Hehehe... But I would say, you don't do the same mistake as me. Maths is very crucial.

Ruman said...

hehe....same here....anyways thnx

arunesh srivastava said...

hey prab..wassup...
tell me...can i convert 12 marks into 12*4...or s'thing like that..
i 'm desperately want to do m.tech...
suggest me some books...or anything if u want to ...
plz..help me i'm much in need..

prab97 said...

Yeah.... Easily. You can convert into 12*6.
12*4 won't guarantee IIT.
Just keep patience while studies for one year and u can convert it into 12*6 without any problems. Practice is the key to success.

arunesh srivastava said...

hey,it's very disguisting abt the iit-b...;i read all u write....
then what u should now....
any other college...
and ur right that there is hardly any student without a back...in b.tech..
do u apply for iii-t allahabad.. it's a good college either,, and near to my college.having good infrastructure...

prab97 said...

The most unethical thing IIIT-Bians did was that they didn't mention this fact in the eligibility criteria at the time of applying. I hate them for this.

Yeah, I've applied in IIIT-A. I've my test on 1st of June there. It is the best IIIT out there. But seats are very less in number. Lets see what happens.

I'm also applying to NIT Trichy headed central counselling in which 6 NITs are participating.

arunesh srivastava said...

hey...wass up ...got some college...

prab97 said...

Yes! I got selected in IIIT-Allahabad! I'll make a blog post sharing my experience soon.

arunesh srivastava said...

hey congrats...it's take almost 1 month to congrats u...
finally u made it so...how u feel there...
one of my seniors is also there pursuing ms name nerrej kumar..
i'm also live almost one kilometer for from the iiit campus....
all the best to u....

prab97 said...

@Arunesh Thanks! I'll try to find your senior once classes start.
And we too may meet someday :)

Unknown said...

hi bro, hw r u
finally u got selected.
congrates!!!!!
are the books that u mention r enough to crack gate??????
i want to appear in gate 2011.

arunesh srivastava said...

hi..wass up... need u favour that.how can i manage the subjects apart from the 4th year subjects...is it possible to just read the subjects and do q's at last..or it should be done parallel with subjects..

prab97 said...

Everything fine here. U say. How is life going?
Yes, u can manage 4th yr parallely. B.Tech papers can be cleared with a one night stand! :p Thats what I did in final yr.
GATE needs more attention. You should concentrate on the basic and fundamental concepts in the subjects as well as solve previous years papers.

By the way, I have a collection of online resources for GATE preparation which I mailed to a few of my acquaintences who are preparing for GATE. If you wish, give me your mail address, I'll forward that mail to you as well.

hi bro..your blog really shows me a pathway..im gate 2011 aspirant.. terribly want to get into IIT's..can you plzz mail me the resources which you used.. i wud be grateful..:)

prab97 said...

My gmail ID is prabhakar97
Just mail me.

hi bro..thanks a lot..ultimateresources..:):) and congrats for making it to iiit..:)good luck:)

prab97 said...

You are most welcome :-)

hello prab..how r u?
i jus wanted some help..im studying theory of computations..but it becomes harder if we go deeper..so is it necessary to learn every theorem..? im stuck here.:(..

prab97 said...

Well, if you feel TOC is tough then you can skip most parts of that.
But do study one topic thoroughly in TOC. And that topic is "Identifying the language and grammar". You can scan through all the previous GATE papers and notice that in every paper there is at least one question related to that. Most year papers have more than 2 questions from that topic. Do study that seriously.

cool..ok i will do that..thanks man:)

arunesh srivastava said...

yeah fine..life is same as it were before..sorry for replying late...yeah i also think that last one month preparation is enough..thanks for ur kindness..my email.id is avi.cindrella@gmail.com.
i'm stuck in the file-indexing in dbms..feeling bored..

prab97 said...

Hi Arunesh. File indexing isn't a big deal. You can master it by studying with Navathe's book and solving the numerical examples therein.
By the way, my article for GATE preparation was published at the URL below. You can access useful online resources from the links at the end of that article.

arunesh srivastava said...

thanks..bro..
these are truly good resources.
ya i follow navathe..i understand it but it bores me...
trying to increase my potential.

arunesh srivastava said...

hey wass up..
do me a favour i am confuse bt'n the galvin and william stallng of os.which one is the best and i have the galvin.

prab97 said...

Galvn is good enough. Stick to it. It is good for you :-)

Shachindra said...

hi Prab, can you please explain me Q.7(the 1 related to dram). Since there are 32 chips, total no of refreshes reqd = 32 * 1000 right. So the total time should be 3200 * 2^10 I think(obviously i know its wrong since the option isn't there. But I would like to knwo where I'm goin wrong). Also, please mail me some resources to sachindraac@gmail.com

Manish Gharat said...

none of the question paper links are working prab.. please if u can repair them...

Saurabh Verma said...

Hey Prab! How come the logic of Q17.

L1-L3 is always recursive which implies L1-L3 is re
The question asked which one is not necessarily true
I think L2 U L3 is not necessarily re always

nikhil said...

hello sir ,myself nikhil i am going through with ur post in ur blog and u have written excellent post regarding gate ...as i am a gate aspirant so i want some tips from u regarding gate preparation....if u tell me that how much time we have to give for gate and how to start preparing for it from scratch as i am a average student not that much brilliant so what i have to do so i can qualify gate with good marks
is it necessary to get coaching ....if not how can i start my preparation on my own as i cant able to decide that frm where to start.....
and plze provide some material for gate preparation if u have........
i will be very thankfull to u ......

An excellent job done by you. No doubt you are great and helpful for visitors those who are related to learning activities.
..................... Excellent

kris said...

q33 shouldnt the OF operation be after the perform operation plz reply !!

kris said...

Q33 shoudnt OP operation be after the PO operation because the ans from perform operations is used in the next instructions

kris said...

Q33 shoudnt OP operation be after the PO operation because the ans from perform operations is used in the next instructions

ravi said...
This comment has been removed by a blog administrator.