Weighing puzzle

This is one gem, that I got from a friend of mine. The puzzle in its simplest form goes like this:

There are a set of 8 balls. Out of which 7 are of same mass, and the remaining one is heavier than the rest. What is the minimum number of weighings required to find out the heavier ball? i.e. How many times do you require to use the balance?

My Method

I do not know what you would do, but what I did was to divide the balls first into groups of two groups of 4 balls, then take the heavier set, and divide it into two parts and so on. This yields an answer of 3. More precisely, the answer is:

where n is the number of balls.

 

Actual Answer

However the actual answer is two weighings. The technique is to split the balls into three approximately equal groups, here we have 3,3,2. Then weigh the 3,3 groups against each other, if they are the same, then weigh the two remaining balls against one another. If one of the two 3,3 groups are heavier, then select that group and weigh any of the two balls against one another, if one is heavy, then you got the ball, if both are equal, then the third one of the group is the heavier.

So the correct expression is

for n balls.

 

Decision Tree

Here is a schematic diagram:

GATE CS 2009 Question Paper

A lot of people are asking for a copy of the GATE 2009 papers. Here is a copy of my GATE CS 2009 paper photographed and merged in DJVU format.

In case you cannot open the file, download the Win DJ View software for Windows.

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.
21. B This was quite simple, you can apply Bayes Theorem, or just use the basic probability theorems.
23. 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".
24. B The function given the the table is P+Q'
25. D
26. B See the corresponding chapter on the book of Discrete Mathematics by Rosen.
27. 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.
28. B Click to view the enlarged image.
29. 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.
31. 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
32. C Consult the OS book by Deitel.
33. A I is true. II is false, as it does not ensure fairness. III is false as there is no queue of sleeping processes.
34. B This is the one and only reason for using multilevel paging. All other benefits are direct or indirect effects of this reason.
35. 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).
36. C Open addressing and linear probing results in table C. Just try it out in pencil and paper.
37. 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.
38. D (a,c) cannot follow (b,c) as (a,c) < (b,c)
39. B
40. 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.
41. C Try generating a few strings.
42. 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.
43. B Draw the dependency graph. S2 and S3 will have no cycles.
47. 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.
48. C Look into any discussion on CRC. I read this from Forouzan.
49. 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
50. D All of the options are true. For I, look into the book of Jalote. others are true from the definition of Cyclomatic Complexity.
51. C 400x2x10x63 + 16x63 + 29 = 505037
52. C 16x63 + 31 = 1039
53. C This is the Longest Common Subsequence problem.
54. B Look into the above link.
55. 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.
56. B Follows from the dependencies and definitions of 3NF.
57. 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.
58. 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
59. C Try constructing the max heap.
60. 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).

If you believe that any of the answers are wrong, or cannot seem to follow the explanation that I have provided, please leave a comment here. I'll try to reply to all the questions.

GATE 2009

The regular readers of this blog are all asking about my absence for such a long time. The sole reason for this is GATE 2009, which took place today. This examination has a lot of importance for me, as the result of this is going to shape up my future career. So a lot of time and energy was devoted to it, resulting in lesser time to other activities like maintaining this blog.

Thankfully GATE 2009 CS paper was easier than expected. There have been some silly mistakes on my part, which could have been avoided, but overall I expect a better ranking than GATE 2008.