Q.1. Let G=(V, E) be a graph. Define $\xi(G) = \sum\limits_d i_d*d$, where $i_d$ is the number of
vertices of degree d in G. If S and T are two different trees with $\xi(S) = \xi(T)$, then
(A) |S| = 2|T|
(B) |S| = |T| - 1
(C) |S| = |T|
(D) |S| = |T| + 1
Sol : $\xi(G)$ basically is the sum of degrees of all vertices in a graph. If sum of degrees of two different trees are same,
then number of nodes in the trees has to be same. We prove this by induction on sum of degree of all vertices in the two trees.
Q.2. Newton-Raphson method is used to compute a root of the equation $x^2 - 13 = 0$
with 3.5 as the initial value. The approximation after one iteration is
(A) 3.575
(B) 3.676
(C) 3.667
(D) 3.607
Sol : We know that, according to Newton-Raphson method,
$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$
In this question $f(x) = x^2-13$, and so $f'(x) = 2x$.
Here current $x_n = 3.5$, $f(x_n) = f(3.5) = -0.75$, and $f'(x_n) = f'(3.5) = 7$. So
$$x_{n+1} = 3.5 - \frac{-0.75}{7} = 3.607$$
So option (D) is correct.
See also Q.2.15 (2002), Q.42 (2003), Q.28 (2007) and Q.22 (2008).
Q.3. What is the possible number of reflexive relations on a set of 5 elements?
(A) $2^{10}$
(B) $2^{15}$
(C) $2^{20}$
(D) $2^{25}$
Sol : Consider a table of size 5*5 in which each possible pair is listed. In a reflexive relation, we must include all 5 diagonal elements. So from rest of the 20 elements, we have choice whether to include them or not. So we have $2^{20}$ possible reflexive relations. So option (C) is correct.
Q.4. Consider the set S = $\{1, ω, ω^2\}$, where $ω$ and $ω^2$ are cube roots of unity. If *
denotes the multiplication operation, the structure (S, *) forms
(A) A Group
(B) A Ring
(C) An integral domain
(D) A field
Sol : We can directly answer this question as "A Group", because other three options require two operations over structure, but let us see whether (S, *) satisfies group properties or not.
Q.5. What is the value of $\lim_{n \to \infty}\left(1 - \frac{1}{n}\right)^{2n}$ ?
(A) 0
(B) $e^{-2}$
(C) $e^{-1/2}$
(D) 1
Sol : We know that $\lim_{n \to \infty}\left(1 - \frac{1}{n}\right)^{n} = e^{-1}$, so $$\lim_{n \to \infty}\left(1 - \frac{1}{n}\right)^{2n} = e^{-2}$$. So option (B) is correct.
Q.26. Consider a company that assembles computers. The probability of a faulty
assembly of any computer is p. The company therefore subjects each
computer to a testing process. This testing process gives the correct result for
any computer with a probability of q. What is the probability of a computer
being declared faulty?
(A) pq + (1 - p)(1 - q)
(B) (1 - q)p
(C) (1 - q)p
(D) pq
Sol : P(declared faulty) = P(actually faulty)*P(declared faulty|actually faulty) +
P(not faulty)*P(declared faulty|not faulty) = p*q + (1-p)*(1-q).
So option (A) is correct.
Q.27. What is the probability that divisor of $10^{99}$ is a multiple of $10^{96}$?
(A) 1/625
(B) 4/625
(C) 12/625
(D) 16/625
Sol : Divisiors of $10^{99}$ are of the form $2^a*5^b$, where a and b can go from 0 to 99 each, so there are 10000 divisors
of $10^{99}$. Now Any of those divisors would be a multiple of $10^{96}$ if both a and b are atleast 96 i.e. 96, 97, 98, or 99.
So each of a and b have 4 choices each, and so there are 16 divisiors which are multiple of $10^{96}$.
So prob = 16/10000 = 1/625, so option (A) is correct.
Q.28. The degree sequence of a simple graph is the sequence of the degrees of the
nodes in the graph in decreasing order. Which of the following sequences can not
be the degree sequence of any graph?
I. 7, 6, 5, 4, 4, 3, 2, 1
II. 6, 6, 6, 6, 3, 3, 2, 2
III. 7, 6, 6, 4, 4, 3, 2, 2
IV. 8, 7, 7, 6, 4, 2, 1, 1
(A) I and II
(B) III and IV
(C) IV only
(D) II and IV
Sol : This can be solved using havel hakimi theorem, which says :
Q.29. Consider the following matrix
$$A = \left[\begin{array}{cc}2 & 3\\x & y \end{array}\right]$$
If the eigenvalues of A are 4 and 8, then
(A) x = 4, y = 10
(B) x = 5, y = 8
(C) x = -3, y = 9
(D) x = -4, y = 10
Sol : Characteristic equation for given matrix is $$(2-λ)(y-λ)-3x = 0$$ Putting λ = 4 and 8, we get 2 equations : $$3x+2y = 8$$ $$3x+6y = 48$$ Solving both equations, we get x = -4, y = 10. So option (D) is correct.
Q.30. Suppose the predicate F(x, y, t) is used to represent the statement that person x
can fool person y at time t. which one of the statements below expresses best
the meaning of the formula ∀x∃y∃t(¬F(x,y,t))?
(A) Everyone can fool some person at some time
(B) No one can fool everyone all the time
(C) Everyone cannot fool some person all the time
(D) No one can fool some person at some time
Sol : The formula ∀x∃y∃t(¬F(x,y,t)) says that for every person x, there exists a person y, and there exists a time t, such that x cannot fool y at time t i.e. No person can fool everyone all the time. So option (B) is correct. Alternatively, you can bring negation outside, thus swapping ∀ and ∃, and so statement becomes ¬(∃x∀y∀t(F(x,y,t)) i.e. there does not exist a person who can fool everyone at everytime, which is again option (B).