GATE 1998 CS question 1.1 (Probability)

1.1. A die is rolled three times. The probability that exactly one odd number turns up among the three outcomes is:
(a) 1/6 (b) 3/8 (c) 1/8 (d) 1/2

Explanation (answer at the end):

Hah, probability!
Ok, let that not deter you, this problem is quite easy.
First of all, what are the numbers on a die? Ok, repeat after me, 1, 2, 3, 4, 5, and 6. :)
How many is that? 6
Now, how many of those are odd? 3
So, when you roll a die once, what is the probability that you get an odd number? (getting one of 3 odd numbers/ getting any one of the 6 numbers on the die) = 3choose1 / 6choose1 = 1/2.
Now, the die does not have any 'memory', so repeated rollings also have the same probability. So now, the probability that you get an odd num in the first rolling is 1/2, and the probability that you get an odd num in the second rolling is also 1/2.
Combining the first and second rollings, the possible combinations are:
(odd, even), (even, odd), (even, even), (odd, odd)
Let's say you wanted it such that both the first and the second rolling must give odd numbers.
That is, you want the combination (odd, odd). Given that odd and even are equally probable, and the rollings of independent of each other, we can see that all the 4 combinations above must have equal probability i.e. 1/4. Therefore, the probability of getting (odd,odd) is 1/4.
Now, extend this to 3 rollings. The combinations go like:
(odd, odd, odd), (odd, odd, even), (odd, even, odd), ...
There are 8 combinations like this (try and count if you don't believe me.. :) ). Using the same argument as above, all 8 are equally probable, so the probability of getting any of them is 1/8.
In particular, we want (odd, odd, odd), and the probability of getting that is also 1/8.
Answer: (c)
I probably got carried away explaining things and forgot the original question while writing that stroked out content. Sorry for the messup, and thanks to the anonymous commenter.
What we actually want is cases where exactly one odd comes up among the rollings. This one odd can come in one of three places as in (odd, even, even), (even, odd, even), and (even, even, odd). So out of the possible 8 combinations, 3 are favourable to us.
So the answer is (b) 3/8

GATE 2000 CS question 1.3 (Matrix Algebra)

1.3. The determinant of the matrix:

2	0	0	0
8	1	7	2
2	0	2	0
9	0	6	1

is:
(a) 4 (b) 0 (c) 15 (d) 20

Explanation (answer at the end):

The method for finding the determinant of any nXn matrix is:
Multiply each element of a main row by the determinant of the matrix formed by removing its row and column from the original matrix.
Ok, that might not have been very clear. I'll explain...
Take one row or column as the 'main' row (or column) for calculation (from here on I'll call it the 'main row', though in some problems choosing a column might be better and so we must do that.) For each element of the main row, find the (n-1)X(n-1) matrix formed by removing the row and column of the current element.
For example, let's choose the first row here. In it, the first element is 2. We now form a 3X3 matrix by removing the row and column in which 2 is present. So, we end up with:

1	7	2
0	2	0
0	6	1

Now, we have to find the determinant of this matrix. The method is again the same, choose a row or column, find the smaller matrix. Now, since we're going to multiply, we can save ourselves some work if we find a row or column with many zeros, because multiplication by them is gonna give only 0's anyway, so we can avoid those calculations.
Here, the first column has all but one element as 0's. So, we choose that one.
The smaller matrix we get now is:

2	0
6	1

The value of this is, 2X1 - 0X6 = 2. Now, we must multiply this by the element of the 3X3 matrix we chose, which is 1. So, 2X1 gives 2 again. Since the other elements of the column are 0, our calculation for this 3X3 matrix ends here.
Now, we have to multiply this 3X3 matrix's determinant value by the element we chose in the original 4X4 matrix. We chose 2 once upon a time, remember?
So, the value now is: 2X2 = 4.
Now, in this case, we were just lucky, and the first row of the original matrix has 0's for all other elements. So, our calculations end here and the answer is 4.
In general, an important rule for solving determinant problems is: choose the row or column that has the maximum number of 0's, in order to minimize calculations.

Answer: (a) 4

GATE 1995 CS question 1.1 (8085 Assembly)

1.1. A single instruction to clear the lower four bits of the accumulator in 8085 assembly language?
(a) XRI FOH (b) ANI FOH (c) XRI FOH (d) ANI OFH

Explanation (answer at the end):

Quite very very easy, if you know the functions of XRI and ANI.
XRI stands for XOR Immediate. It tells the processor "I'll give you an operand immediately now, XOR it with the Accumulator and put the result in Accumulator itself".
ANI is similar, it says: "I'll give you an operand immediately now, do an AND operation between it and the Accumulator and put the result in Accumulator itself".
Here, we want to clear some bits. Since XOR operation's output always depends on both the operands, it can't be the answer. So, we're left with (b) and (d).
Now, in the AND operator, if one of the operands is a 1, the result is the value of the other operand.
And if one of the operands is 0, the result is 0, whatever the value of the other operand.
From this, we can see that in order to clear some bits (i.e., set them to 0), we have to AND them with 0.
In the question, they say 'lower four bits', which mean the bits to the right hand side (bits in the right hand side have less value, so are considered 'lower'.) So, in order to clear those bits, the 0's in the operand should also be in the right hand side.
Hence, ANI FOH is the answer. Here, each hexadecimal digit corresponds to four bits, so the operand is actually 1111 0000 in binary. Because of this, the lower four bits get cleared.

Answer: (b)

GATE 2000 CS question 1.1 (Probability)

1.1. The mininum number of cards to be dealt from an arbitrarily shuffled deck of 52 cards, to guarantee that three cards are from some same suite is:
(a) 3 (b) 8 (c) 9 (d) 12

Explanation (answer at the end):

This is a standard cards problem, and the solution is quite easy. First of all, there are 4 suites in a deck of cards (usually called Spades, Clubs, Hearts and Diamonds, though several other names also have been given to them). Each suite has 13 cards in it.

We want a guarantee that three cards from the same suite come to us, we shall assume the worst case and ensure 3 cards of same suite occur even in that case.

The worst case here is that, as we pick cards, each card is of a different type. In that case, with the first 4 picks, we'd have taken one card of each suite. With the next 4 cards, we'd have 2 cards of each suite. Now, if we pick another card, whatever suite it may be, we have 2 other cards of that suite already. So, we now have 3 cards of the same suite, which was our objective!!

So, from the above, it's clear that to guarantee that three cards are from some same suite, we have to pick 9 cards from the deck.

Answer: (c)

Previous year GATE paper and GATE resources

I'm a student preparing for the GATE 2009 exam. I'm taking the exam in the CS stream, and I thought it would benefit a lot of people if I shared what I learn with everyone. So, as and when I learn things, solve new problems, find new ways to do things, I'll share it with you.

There are a lot of excellent resources on the net for preparing for the GATE exam, especially if you are preparing for the exam in CS (Computer Science).

I've found a few, and thought of sharing them with you:

• Previous years' GATE question papers (papers for all streams are available for download here):
  http://www.gateforum.com/gate_papers.php
  For each year, right click on the Open link near CS, and choose 'Save page as...' to save the pdf which contains the question paper.
• A LOT of resources for preparing for GATE in the CS stream. The page says resources for CS, EE, etc., but atleast 75% are for the computer science stream:
  http://www.gateforum.com/resources.html (UPDATE: This page unfortunately seems to have vanished now, kindly comment if you know its current location)
  
  There are subjectwise links at the beginning, but very useful links are present far below these in the 'Downloads Section'. For example, there is a Formulae quick reference that lists almost all formulae you might need for GATE problems.
  
• MIT's Introduction to algorithm lecture videos. These give an excellent preparation for the algorithm sections.
• A student who listened to the above lectures has put up a blog explaining some of the material and given out his notes. An excellent supplement to the videos (and those who cannot access the videos due to slow connections can get atleast part of the benefit from reading these).
  http://www.catonmat.net/blog/mit-introduction-to-algorithms-part-one/
  
  

I'll keep posting more resources as and when I find them.
Keep in touch. :)