Monday, February 09, 2009

GATE 2009 CS Solutions

There seems to be a lot of arguments over the GATE CS 2009 solutions. Here is my version of it. I have provided explanations and diagrams wherever I felt them necessary.

1. A Follows directly from the definition of a Group.
2. A A look at this figure should clear your doubts:
3. B I did this in the lame way, by drawing graphs. I am quite sure that it can be proved mathematically too. Something along the lines of "let all the vertices have dissimilar degrees", and then proof by contradiction.
4. D Not symmetric as (x,y) is present but (y,x) is absent. Not anti-symmetric as (x,z) and (z,x) are both present.
5. B This one was quite simple, just use base convert function of your calculator. Alternatively use the age old method of grouping the binary digits in groups of 3.
6. B Draw the K-Map and group 0s taking 2 0s per group. You should get 2 such groups. Each group requires one NOR gate. Then these 2 groups, together will require another NOR gate. Formally it looks like: AB+C = (A+C)(B+C) = ( (A+C) (B+C) )'' = ( (A+C)' + (B+C)' )'
7. C We need 256 Kbytes = 256 x 1024 x 8 bits. We have RAM chips of capacity 32 Kbits = 32 x 1024 bits. Dive the former by latter, and you arrive at 64 chips.
8. C I do not remember where I read it from, but I guess its either in 8085 book by Gaonkar or in the Architecture book by Hayes. you can also try Mano's book.
9. A Belady's anomaly is a typical (and very odd) feature of FIFO. Its explained nicely in Galvin.
10. B Page frame numbers are most important. Virtual page numbers may not be stored entirely in the page table.
11. A In each pass, there can be at most 1 swap. There are n such passes.
12. B This is evident from the grammar itself. Just try generating some strings, if you feel otherwise.
13. C* I am sure about the Q part. Q is true. But I have some confusion over the P part. P can be shown to be false for certain directed graphs. But from the general definition of Graph, directed is not to be assumed. So I hope P & Q both are true. personally I did not answer this question.
14. C This is best explained by the set diagram (original diagram in the book of Algorithms by Horowitz & Sahani.
15. C This is again evident from the RE given. The string must have at least two 0s.
16. D Some CFLs cannot be accepted by Deterministic PDAs. I got this from the book of Automata book of Hopcroft, Motwani and Ullman.
17. B Check out the Dragon book (Compilers by Aho, Sethi, Ullman)
18. B Just dry run the GATE_09_18.c program. Giving the steps would be laborious for me. In case you want to just see how it works, try running the program.
19. C I do not know from which book this was given. Thankfully it was there in my SW Engg paper that I appeared for in 2008.
20. B This was quite simple, you can apply Bayes Theorem, or just use the basic probability theorems.
21. D Gold and Silver does not literally translate to "G(x) AND S(x)". it means that "All ornaments which are made of Gold or Silver are precious".
22. B The function given the the table is P+Q'
23. D
24. B See the corresponding chapter on the book of Discrete Mathematics by Rosen.
25. A Look at the transition diagram: State 00 means A=0 and B=0. State 11 has not been drawn as it cannot be reached from any other state. The smallest input satisfying the criterion is 101.
26. B Click to view the enlarged image.
27. D 4 way set associative cache with 16 blocks imply that each set has 4 blocks numbered 0,1,2,3. We take each memory block and use the last 2 bits to place it into proper cache following LRU replacement scheme. 216 would not be in cache as it is followed by 8, 48, 32 and 92.
28. B Initial position of head = 50. Nearest request is 34. The sequence of access would be: 50, 34, 20, 19, 15, 10, 7, 4, 2, 73
29. C Consult the OS book by Deitel.
30. A I is true. II is false, as it does not ensure fairness. III is false as there is no queue of sleeping processes.
31. B This is the one and only reason for using multilevel paging. All other benefits are direct or indirect effects of this reason.
32. B The equation is of the form: T(n) = T(n/3) + cn On solving this recurrence relation we get T(n) = Big_Theta (n log n) Without going into the details of the proof, let me give you something that wil explain it much more naturally. Just download GATE_09_CS_Q35.pdf, where I have shown the data plotted against various values of c {5,10,15,20,25} and n {1,3,9, ... 3^11}. Then I have plotted n*log(n,b_up) and n*log(n,b_dn) as the two lines that give the upper and lower bound for the series for some values of bases b_up and b_dn. Most importantly the nature of the curves are similar to that of type n*log(n).
33. C Open addressing and linear probing results in table C. Just try it out in pencil and paper.
34. B The minimum number of nodes required for an AVL tree of height h is given by, F(h) = F(h-1) + F(h-2) + 1, where F(0) = 1 and F(1) = 2. For the deduction of this expressions, look into the book by Kruse.
35. D (a,c) cannot follow (b,c) as (a,c) < (b,c)
36. B
37. C This follows directly from the property of CFGs, where we see that CFGs are not closed under intersection, but produces CFGs when intersected with RLs. Even if you are not aware of this, just examine the languages L1 and L2. The intersection is given by (a^m)(b^m)c. This is obviously a CFG.
38. C Try generating a few strings.
39. B I is true for simple languages like assembly language of 8085. II is false, dynamic allocation is a must for implementing recursion. III is true as written in the Dragon book. IV is true.
40. B Draw the dependency graph. S2 and S3 will have no cycles.
41. A Maximum packet lifetime is 64s and the number of packets can range from 0 to 2^32-1 and the counter increments by 1 per millisecond. Thus the minimum permissible rate is 0.0149.
42. C Look into any discussion on CRC. I read this from Forouzan.
43. C I is true II is false, it is to be defined only in level 0 and 1 III is true IV is false, data stores cannot be connected between each other
44. D All of the options are true. For I, look into the book of Jalote. others are true from the definition of Cyclomatic Complexity.
45. C 400x2x10x63 + 16x63 + 29 = 505037
46. C 16x63 + 31 = 1039
47. C This is the Longest Common Subsequence problem.
48. B Look into the above link.
49. D B and C are clearly wrong. Amongst A and D, D is chosen as it also returns suppliers who have not supplied any part.
50. B Follows from the dependencies and definitions of 3NF.
51. D Let n be the number of frames. Then, 25e-3 = 100n / 1e6, which gives the value of n = 25. Thus we need ceiling (log 25 / log 2) = 5 bits.
52. B Time taken to send 2^5 frames = 32. Time taken for the first fram to be acknowledged = 25x2. Thus waiting time = 50-32 = 18
53. C Try constructing the max heap.
54. D In case of the 1st deletion there is no problem. In case of the 2nd deletion, the tree loses its almost complete nature, thus we have to replace 8 in a proper place in order to retain this property.

The * mark indicates that I am not sure about the answer to that question. Please keep in mind that the answers may not be correct. These are what I believe to be correct. Most of them were computed by me, and some of them are from fellow GATE aspirants (mostly Sukanto).

1. i have different in q 35.
T(n)=T(3)+cn+c(n/3)+c(n/3^2)... i terms
where n/3^i=3 or i=log n - 1
T(n)=cn(1-(1/3)^i)/(1-1/3)
=cn(1-(3-n))
=cn^2.

1. You know the recurrence relation of quick-sort?
T(n) = 2*T(n/2)+O(n)

This results in T(n) = Theta(n log n)

Q35 is also along similar lines. In your proof, i = log(n) base 3, try using that and you will reach the same conclusion.

2. why don't you guys just use master theorem, it falls under case 2.. n ans is Theta(n log n)

3. why don't u guys just use master theorem here.. it falls under case 2 and ans is Theta(n log n)

2. Well Sumit, your prove is not at all clear to me. I guess, without proper mathematical notation (which is unavailable for posting in blogs like this) it is really difficult to understand it.

However, I am quite convinced that the answer to be Big_Theta(n*log n), which I have further clarified with a diagram.

Hope it helps you.

3. regarding 35
when solved with masters theorm the answer comes as o(n)......

4. I personally do not use the Akra-Bazzi theorem (popularly known as Master's theorem) for recurrence relations. But I'm sure that there must be some sort of mistake in your usage of the theorem.

The method that I have used to compute the solution is the most natural. I computed specific values of T(n) and drew the graph (which I attached). The nature of the curve is similar to that of n*log(n).

If I have time, I will look into the formal proof of the same. But the answer is beyond doubt.

5. But in the exam it is not possible to compute in that way........even if it's possible it's time consuming..........so, we need a less time consuming method.....hence inclined to use master's theorm......But i'am quite sure using master's the answer is bound to come o(n)......can't say about other methods.....

6. I guess its futile arguing on Q35 with Suvadeep, till either he or I come up with a formal proof of the same.

I will put it up, if I have it.

7. Guys,please dont give dumb explanations whatever comes to ur mind.It creates lot of confusions to innocent students.Kenneth rosen(Discrete mathematics and its applications) standard theorem say it is O(n).Dont know why someone argues as O(nlogn) and another as O(n^2).

8. @ Canon,

Please do not call other's opinion's "dumb explanations" without any proper reference. I have uploaded the PDF file which clearly shows the answer to be O(nlog n). If you have the exact proof of O(n), please share it with us, or give the reference. Please note that the Master's Theorem, cannot be applied here.

9. I solved it using Akra-Bazzi method and the result is O(n) as others have already said.

10. hii frnds..i think the answer for 7th Question is: 8 chips
256 * 1024 / 32 *1024 = 8 chips..

11. Also i need answer for 10th question
wat i read in William Stallings is

Paging:
Page table contains Frame numbers

Segmentation:
Page table contains Length of the segment and Starting address of the segment..

12. why are u guys so confused about the soln of q35.....?

here is the answer that i am proposing regardin theta(n)

1. t(n)=t(n/3) + cn

2. t(n)=t(n/3^2) + c(n/3) + cn

let us take...n=3^k...

then this reducing iteration will continue...till t(3)....where this value will be replaced by "n" as given in the paper.

then at that stage...

t(n)= t(3)+ c[ (3^2) + (3^3) +.......(3^k)]........(A)

u can get this condition by iterating more times...till

1. [n/(3^x)]=3

2. [(3^k)/(3^x)]=3

which is possible when
x=(3^(k-1)) [3 to the power k-1]

1. n/(3^k-2)=3^2
2. n/(3^k-3)=3^3
...
like that we will continue to calculate last step of iteration.

now using eqn (A)

t(n)= t(3)+
c[ (3^2)({3^(k-2)}-1)/(3-1)]

{applying summation of G.P.}

t(n) will be (puttin t(3)=n)

t(n)=n + c[{(3^k)-(3^2)}/2]

now put 3^k = n

t(n)=n+c[(n-9)/2]

so guys what about its order...

t(n)= theta(n)......

best of luck for gate2010

tc!!

13. Hi Bigyan,

Regarding question number 35. I have different opinion. I am getting answer as 'A'

T(n) = T(n/3) + cn

is O(n). May be I am wrong. I plotted the graph for the recursion and lower_bound as f(n) = n and upper_bound as f(n) = 3 * c * n.

and recursion value always lie between lower_bound and upper_bound.

#include
#include

int c;

double X(double num)
{
if (num <= 3) {
return num;
}

return (X(num * 1.0 /3) + c*num);
}

int main()
{
double num;
double ret;

for (c = 5; c <= 25; c += 5)
{
printf("c %d\n", c);
for (num = 2187; num <= 177147 * 81 * 81; num *= 3)
{
ret = X(num);
printf("num %lf ret %lf upper %lf val %d \n", num, ret, 3 * c * num, (ret <= 3 * c *num) ? 1 : 0 );

}
}
}

Mathematics proof:

T(n) = T(n/3) + cn

For first call cost will be cn, for second call cost will be cn/3, then cn/9, cn/27 and so on and the last cost is n.

Total

T(n) = cn + cn/3 + cn/9 + cn/27....... + n (for the last cost.

T(n) <= cn + cn/3 + cn/9 + cn/27 ...... + cn

T(n) <= cn + cn(1/(1 - 1/3))

T(n) <= cn + cn*3/2

T(n) <= 5*c*n/2

T(n) <= 3*c*n

appreciate your comment on the same.

Thanks,
Rupesh Bajaj

14. Please, explain me Q 18

I am not able to understand it

1. The easiest way to understand this kind of program is to type it out and debug it step by step.

15. @lavankohsa ... Sorry pal, its been 3.5 years since I have see the question paper. If you let me know where are you not understanding, I will try to help you out.

16. Nice Post..I have referred your page from GATE Community website ... https://www.facebook.com/#!/groups/114609428571319/

17. Hi,
Can you please explain me the solution of question no 43 which is on conflict serializability,which ones among the four options are conflict serializable??...i have found all the four dependency graphs with no cycles..

18. @Shatabdi, I do not have access to the GATE 2009 CS paper. If you can forward the question to my email, I can have a look at it.

19. Hi, Can you please explain in detail Q21 that is a probability question. Thanks.

1. Given:
P(odd) = 0.9*P(even)

We know:
P(odd) + P(even) = 1

Hence:
P(even) = 10/19
P(odd) = 9/19

Hence:
P(2) = P(4) = P(6) = (1/3)*(10/19) = 10/57
Similarly,
P(1) = P(3) = P(5) = 3/19

Given:
0.75 = P(face is even and >3)/P(face is >3)
=> P(face is >3) = (1/0.75)*P(face is even and >3)
= (4/3)*[P(4)+P(6)]
= (4/3)*(20/57)
= 0.4678

20. q-47 ans is .064

21. Hello, Could you care to explain Question 47? I'm missing something!

Thanks!

22. hello, in question 40 i think answer should be B . because only language that comes after intersection is L={c} there is no other string possible in this intersection and this is a regular language .. please explain.

23. hiiiii Regarding Q 43..
Schedule 2 can not be transformed to a serial schedule by swapping the non conflicting instructions of both the transaction.

So, I think the answer is only C.

24. Regarding q no. 43.
Since schedule 2 can not be transformed to a serial schedule by swapping the non conflicting instructions of both the transaction. So, I think the answer is C.

I'd love to hear from you !