Monday, March 23, 2009

GATE 2002 CS question 2.16 (Probability)

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)

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)

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)

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)

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

Sunday, March 22, 2009

GATE 2002 CS question 1.1 (Matrix Algebra)

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