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

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