GATE India (CS)

GATE 1999 CS question 1.1 (Probability)

2009-10-31T03:03:00.001+05:30

1.1 Suppose the expectation of a random variable X is 5. Which of the following is true?
(a) There is a sample point at which X has a value 5.
(b) There is a sample point at which X has a value greater than 5.
(c) There is a sample point at which X has a value greater than or equal to 5.
(d) None of the above

First of all, what is this ‘expectation of a random variable’ business?
Well, an ‘expectation’ is a sort of sum – it’s a ‘weighted’ sum. As a formula, it is

E = summation of xi*pi

where xi are the sample points (different values taken) of the random variable, and pi are the probabilities of each value in turn.
Imagine you were a gambler and also happened to know a dice maker. You tell him to make the dice such that numbers 1 to 4 appear with probability 1/12 each, while 5 and 6 appear with probability 1/3 each (verify that this adds up to a total probability of 1). Now, what is the ‘expected value’ of this dice? Well, as I said, expectation is a weighted sum, with the weights being the probabilities. So here, it would be

E = 1*1/12 + 2*1/12 + 3*1/12 + 4*1/12 + 5*1/3 + 6*1/3

E = 4.5

Ha, what is this, the expected value of the dice roll is 4.5? How can a dice roll a non-integer value?
Well, this mathematical expected value isn’t really the expected value of the dice. Yeah, that’s how strange math is. :)
Intuitively, it’s actually a value we try to find such that the difference between the actual value of the random variable and this value is minimum. Now, since we don’t really know the actual value of the random variable beforehand, we keep this value close to the most probable values while not getting too distant from the other values. That is why we got a 4.5 above – it’s a compromise between the high probability of 5 and 6 and the low probabilities of 1,2,3 and 4.
Ok, that’s about the basics of expectation, now let’s dive into this problem. Here, they say that the expectation of a random variable is 5. Well now, let’s think through the options.
Consider (a). Do we really need one of the sample points to be 5 to get an expectation of 5? What about the expectation of an RV (random variable) that takes values 3,4,6,7 with equal probabilities? By now you must be able to calculate and tell that it’s 5. So, (a) is false.
What about (b) then? Well, that appears about right, doesn’t it? A variable which takes only values 1, 2, 3, and 4 can never have an expectation of 5. Even a variable which takes values 4 and 5 with non-zero probabilities for each can’t have an expected value of 5: 4*(something less than 1) + 5*(something less than 1) can never give you 5, only 5*1.0 gives 5. So, is (b) the answer?
But wait, I said 5*1.0 at the last there, can we make the expectation equal to that? Ah, clever idea. What do we need for that? The ‘summation of xi*pi’ should be just 5*1.0 which means there is only one sample point ‘5’ with probability 1.0. In this case, the expectation is of course 5.
So, it's not necessary that there is a sample point greater than 5 - a single sample point at 5 itself also gives that same expectation.
So, the answer is (c) There is a sample point at which X has a value greater than or equal to 5.

GATE 2001 CS question 1.1 (Matrix Algebra)

2009-04-09T22:07:00.010+05:30

1.1 Consider the following statements:
S1: The sum of two singular n X n matrices may be non-singular.
S2: The sum of two n X n non-singular matrices may be singular.
Which of the following statements is correct?
(a) S1 and S2 are both true. (b) S1 is true, S2 is false.
(c) S1 is false, S2 is true. (d) S1 and S2 are both false.

This is one problem where getting too theoretical can get you stuck. Instead, let's try to come up with simple examples. The one I immediately thought of for S1 was:

1	1
1	1

and

1	-1
-1	1

Both these matrices are singular. What does 'singular' mean? It simply means that the determinant of the matrix is zero (if you don't remember how the determinant of a matrix is found, please see this post). Now, what is their matrix sum? It is:

2	0
0	2

Now quick, what is the determinant value of this one? It's 2 X 2 - 0 X 0 = 4. Clearly, this sum is not 0, so the resulting matrix is non-singular. So, we've proved that S1 is true. The second case is still easier. Let's take the matrices

1	0
0	1

and

-1	0
0	-1

Now, both of them have a determinant value of 1, and so they are not singular. What's their matrix sum then?

0	0
0	0

Wow! That's very clearly a singular matrix - it's determinant can't be anything other than 0. So, two non-singular matrices can also give a singular matrix on addition. This means that S2 is also true.

So, the answer is: (a) S1 and S2 are both true

GATE 2002 CS question 2.16 (Probability)

2009-03-23T08:17:00.004+05:30

2.16 Four fair coins are tossed simultaneously. The probability that atleast one head and one tail turn up is
(a) 1/16 (b) 1/8 (c) 7/8 (d) 15/16

This question is somewhat similar to the 1998 GATE paper's 1.1 question. Please read that one if you haven't yet.

Like there, the total number of combinations consisting of {tail, tail, tail, tail}, {tail, tail, tail, tail, head}, ... {head, head, head, head} comes to 2X2X2X2 = 16.

In case you didn't get how, there are two values for the first toss - head or tail. For each of these values, the second toss can give a head or a tail. So now we have 2X2 = 4 combinations. Extend this to 4 tosses and you can see how 16 came up.

Of these 16 combinations, how many satisfy the condition given in the question? To find that, we have to first understand clearly what the question says.

It asks for "the probability that at least one head and one tail turn up". That means in our result set, all the combinations must have at least one head and one tail.

With a little bit of thought, we'll see that there are many more combinations which do have one head and one tail than those which don't have. So, instead of asking what all combinations have that property, let's now try to find which combinations don't have that property.

Let's take some combination out of the pool: say a combination that has one head alone. When we say it has only one head, it immediately means that the others are all tails. So, it has 'atleast' one head and one tail, so it satisfies the condition. Similar to this case of combinations having only one head, any other combinations that have two heads or three heads also have at least one tail, so they also satisfy the condition.

The case of the combinations having four heads is a curious one. Actually, I must have said combination, not combinations, because there is only one: {head, head, head, head}. In this case, there's no 'at least one tail', which means it does not satisfy the condition. So we have one combination where the condition fails.

So, that's it? Out of 16, one doesn't satisfy it, so 15 satisfy it, so the answer is 15/16.

NO! The condition in the question was symmetric - 'at least one head and tail' - which means the answer will also be symmetric. We talked about the all heads combination, what about the all tails one?

Oooh.. Seems we were about to miss something. The all tails combination too fails the condition. Any other combination has a mixture of heads and tails, so will satisfy the condition.

So, the number of combinations that do satisfy the condition is 16 - 2 = 14. To find the probability of the condition being satisfied, divide the number of cases where the condition is satisfied by the total number of cases. Here it is 14/16 = 7/8.

And so, the answer is: (c) 7/8

GATE 2002 CS question 1.14 (Number systems)

2009-03-23T00:59:00.005+05:30

1.14 The decimal value of 0.25
(a) is equivalent to the binary value 0.1
(b) is equivalent to the binary value 0.01
(c) is equivalent to the binary value 0.00111...
(d) cannot be represented precisely in binary

This question must take only half a second if you know how to approach it.
The usual way of converting a decimal fraction to a binary one is to multiply it by 2, take the integer part, rinse and repeat.

Well, here we are not going to use that. Instead, we're going to be clever and use the meaning of number systems.
What is the value of 10 binary? It is 1 * 2^1 + 0 * 2^0. That is, we use decreasing powers of 2 as we move right.

Now, what is 0.1 binary? It is 1 * 2^(-1) which is 1/2. Similarly, 0.01 is 1 * 2^(-2) = 1/4 = 0.25.

Hey, haven't we arrived at the answer then? If 0.01 binary is 0.25 decimal, the answer we need is 0.01.

Yes, but there's something more we can learn here: if you manage to write any fractional value as the sum of 1/(powers of 2), you can directly write down its binary value. In some cases this might prove to save a lot of time. For example, if you asked to find the binary value of say 0.375, we see that it can be written as 0.25 + 0.125, so the answer is 0.011.

In this case, no such splitting was necessary. So, the answer to this question is: (b) is equivalent to the binary value 0.01

GATE 2002 CS question 1.8 (Propositional logic)

2009-03-23T00:45:00.004+05:30

1.8 "If X then Y unless Z" is represented by which of the following formulae in propositional logic?
(a) (X ^ ¬Z) → Y (b) (X^Y)→ ¬Z (c) X → (Y^ ¬Z) (d) (X →Y) ^ ¬Z

Ok, let's first be clear what that statement means: If X then Y unless Z.
In English, A unless B means that A will be true provided B is not true.
So here, the unless means that X being true implies Y also being true, except when Z is true.
So, for Y to be true, we need both X to be true and Z to be false.
This is best expressed by (a) - it literally reads as (X AND NOT(Z)) implies Y.
So, the answer is (a) (X ^ ¬Z) → Y

GATE 2002 CS question 1.6 (Group theory)

2009-03-23T00:13:00.004+05:30

1.6 Which of the following is true?
(a) The set of all rational negative numbers forms a group under multiplication
(b) The set of all non-singular matrices forms a group under multiplication
(c) The set of all matrices forms a group under multiplication
(d) Both B and C are true

To answer this question, we must know what a 'group' is.
In maths, a group is a set of things along with an 'operation' on them that are in such a way that:

(i) whenever you apply the operation to any element (or elements) of the set, you get another element of the same set.
For eg., let's take the set of integers and the operation of multiplication. Whenever you multiply two integers, you always end up with another integer. So this group (which consists of the set of integers and multiplication) satisfies this property. And the property is called 'closure'.

(ii) when the same operation is applied in an expression more than one time, the order in which you do the operations doesn't matter.
For eg., in the same group as above, let's say we have a*b*c (a,b,c being integers and * representing multiplication). Then, we all know that it doesn't matter whether we do (a*b)*c or a*(b*c), the result will be the same. This property is fancily known as 'associativity'.

(iii) there's a particular element, say 'i', such that doing the operation on any other element, say 'x', with this 'i' will again return 'x'. That just means that the operation leaves the element 'x' unchanged, when the other operand is 'i'.
If that seems complicated, after the example you'll see it's a very simple thing. In the same group as above, take any element of the set of integers, multiply it by 1, you'd get the same element right? That is what this property says. It tries to generalize it by saying that for any group, there must be an element in the set which leaves the other element unchanged when the operation is applied on them both. This element is called the 'identity element' and the property is aptly called the 'identity' property.

(iv) for any element 'x' in the set, there exists another element say 'y', such that when the operation is applied on these two, we get the identity element. This 'other element' y is called the inverse of x, and the property is called invertibility.
Let's try this property in the same old group: what is the inverse of 6? Oops... It is 1/6 (since 6 * 1/6 = 1), and that surely isn't in the set of integers. So, this doesn't satisfy the invertibility property, so what we've been calling a group all along is not a group at all! (it's a monoid, in case you're interested)

Now that we have an idea of what a group is, let's attack the original question:

In (a), multiplying a negative number with another gives us a positive number which is outside the set. Hence closure itself isn't satisfied, so it's not a group.

Let's analyze (b). Multiplying two matrices gives another matrix, so closure is there. (A*B)*C is the same as A*(B*C) in matrices too, so associativity also works. You'd have heard of this I matrix which has 1's in the diagonal and 0's everywhere else, and gives the same matrix when multiplied i.e. A*I = A for all A. So that's our identity element. And given that the matrices are non-singular (which means their determinant is not zero), inverse exists for all of them. Hence invertibility too holds. So, it seems this is the group we want.

So, what's wrong in (c)? Well, by saying 'all matrices', it has included singular matrices too, which do not have an inverse. So, it cannot form a group.

Hence, (b) The set of all non-singular matrices forms a group under multiplication is the answer.

GATE 2002 CS question 1.5 (Algorithm Analysis)

2009-03-23T00:01:00.005+05:30

1.5 In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is:
(a) log n (b) n/2 (c) log2(n) - 1 (d) n

Here, we need to search for the element in a singly linked list. So, we can't use a search such as binary search, as we have no way of directly 'jumping' to the middle element.
Hence, log(n) is not possible.
n/2 would be the answer if they had asked for the average case.
However, here they're asking for the 'worst case'. The worst case in a singly linked list is when what we want to search for happens to be at the last of the list: then, we'd have to travel through the entire list to get to that element.
Hence, in the worst case, we'd have to do n comparisons - with each of the n elements of the list, before we finally find it.
So the answer is (d) n

GATE 2002 CS question 1.1 (Matrix Algebra)

2009-03-22T23:42:00.004+05:30

1.1 The rank of the matrix
1 1

0 0
is:
(a) 4 (b) 2 (c) 1 (d) 0

What's this 'rank' of a matrix? Well, it's the count of how many rows of the matrix can stand independently. What that means is: how many rows there are such that they cannot be formed just by multiplying other rows by something and adding them up.
Here, it is obvious that the second row can be obtained by multiplying the first row by 0. So, the rank is 1.
Another, maybe clearer, way to arrive at the same answer is: the row rank of any matrix (what we found above) is equal to its column rank. Here, we see that the two columns are equal. So, the second column is 'dependent' on the first column (or you may take it the reverse way). Either way, there's only one 'independent' column, hence the column rank is 1.
Here the answer is (c) 1

GATE 1998 CS question 1.1 (Probability)

2008-12-31T10:57:00.006+05:30

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)

2008-12-30T15:17:00.005+05:30

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)

2008-12-30T14:06:00.007+05:30

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)

2008-12-26T09:58:00.007+05:30

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

2008-12-04T18:29:00.003+05:30

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. :)