GATE Breaker

A two-faced fair coin has its faces designated as head (H) and tail (T). This coin is tossed three times in succession to record the following outcomes: H, H, H. If the coin is tossed one more time, find the probability (up to one decimal place) of obtaining H again, given the previous realizations of H, H, and H?  (GATE 2017)  Answer: 0.5  Explanation:  Here, the probability of getting one H is $= \dfrac{1}{2}$.  The probability of getting (H, H, H) is  $= \dfrac{1}{2} \times \dfrac{1}{2} \times \dfrac{1}{2}$  $= \dfrac{1}{16}$  The probability of getting (H, H, H, H) is  $= \dfrac{1}{2} \times \dfrac{1}{2} \times \dfrac{1}{2} \times \dfrac{1}{2}$  $= \dfrac{1}{32}$  Therefore, the required probability is  $= \dfrac{\dfrac{1}{16}}{\dfrac{1}{8}}$  $= \dfrac{1}{2}$  $= 0.5$  Previous Post Next Post

If a random variable $X$ has a Poisson distribution with mean 5, then find the expectation $E[(X + 2)^2]$.  (GATE 2017)  Answer: 54  Explanation:  Here, $X$ is a random variable that follows a Poisson distribution with mean $E(X) = 5$.  Therefore, its variance $Var(X) = 5$.  Now, $Var(X) = E(X^2) - \big\{E(X)\big\}^2$   $\Rightarrow E(X^2) = 5 + 5^2$  $\Rightarrow E(X^2) = 30$  Therefore, $E[(X + 2)^2] $  $= E(X^2 + 4X + 4)$  $= E(X^2) + E(4X) + E(4)$  $= E(X^2) + 4E(X) + 4$  $= 30 + 4 \times 5 + 4$  $= 54$  Previous Post Next Post

For the function $f(x) = a + bx$, $0 \leq x \leq 1$, to be valid probability density function, which one of the following statements is correct?  (A) $a = 1$, $b = 4$  (B)  $a = 0.5$, $b = 1$  (C)  $a = 0$, $b = 1$  (D)  $a = 1$, $b = -1$  (GATE 2017)  Answer: ( B)  $a = 0.5$, $b = 1$  Explanation:  For the function $f(x)$ to be a valid probability density function (PDF), the following must hold:  $\int\limits_{0}^{1} f(x) = 1$  $\Rightarrow \int\limits_{0}^{1} (a + bx) = 1$  $\Rightarrow \Big[ax + \dfrac{bx^2}{2}\Big]_{0}^{1} = 1$  $\Rightarrow a + \dfrac{b}{2} = 1$  Only option (B)  $a = 0.5$, $b = 1$ satisfies the above equation.  Previous Post Next Post

Havel-Hakimi Theorem In this tutorial, we will learn how to determine if a given degree sequence can form a simple graph using Havel-Hakimi theorem . A graph is said to be a simple graph if it has no self-loop and parallel edges. For a given graph, it is always possible to find its degree sequence, but it may or may not be possible to draw a graph for a given degree sequence.  A degree sequence is called a  graphic sequence  if a simple graph can be drawn with that sequence. For example, the degree sequence <2, 2, 2> is graphic.  Theorem:  The nonincreasing sequence $<d_1, d_2, \ldots, d_n>$ is graphic if and only if the sequence $(d_2-1,d_3-1, \ldots, d_{d_1+1}-1, d_{d_1+2}, d_{d_1+3}, \ldots, d_n)$ is also graphic.  Note: A sequence with all zeroes is always graphic because we can draw that many isolated vertices.  Based on the above theorem, we can use the following algorithm to draw a simple graph from a given degree sequenc...

Address Calculation in an Array  This tutorial is written for the GATE aspirants. At first, we discuss how to calculate an address in an array, and then we understand the concepts with some examples.  Arrays can be of two types: one-dimensional and two-dimensional. The address calculation takes different formula for these two types of arrays.  One-dimensional Array Let $A[lb,ub]$ be a one-dimensional array, where $lb$ and $ub$ are the starting and ending indices.  Suppose $b$ represents the base address of the array $A$, and $c$ is the size of each element in $A$.  Now, the address of the $i$-th element in $A$ can be computed using the following formula:  $$Address(A[i]) = b + (i - lb)*c.$$  Two-dimensional Array Let $A[lb_1,ub_1][lb_2,ub_2]$ be a two-dimensional array of order $m \times n$, where $lb_1$ and $ub_1$ are the starting and ending row indices, and  $lb_2$ and $ub_2$ are the starting and ending column indices.  Suppose $b$ rep...

The truth table  represents the Boolean function  (A) $X$  (B) $X + Y$  (C) $X \bigoplus  Y$  (D) $Y$  (GATE 2012)  Answer: (A) $X$  Explanation:  From the given truth table, we get  $f(X, Y)$  $= XY' + XY$  $= X(Y' + Y)$  $=X$  Previous Post Next Post

 The minterm expansion of $f(P, Q, R) = PQ + QR' + PR'$ is  (A) $m_2 + m_4 + m_6 + m_7$  (B) $m_0 + m_1 + m_3 + m_5$  (C) $m_0 + m_1 + m_6 + m_7$  (D) $m_2 + m_3 + m_4 +m_5$  (GATE 2010)  Answer: (A) $m_2 + m_4 + m_6 + m_7$  Explanation:  $f(P, Q, R)$  $= PQ + QR' + PR'$  $= PQ(R + R') + (P + P')QR' + P(Q + Q')R'$, since $A + A' = 1$  $= PQR + PQR' + PQR' + P'QR' + PQR' + PQ'R'$  $= PQR + PQR' + P'QR' + PQ'R'$, since $A + A = A$  $= m_7 + m_6 + m_2 + m_4$   Previous Post Next Post

If $P$, $Q$, $R$ are Boolean variables, then $(P + Q')( PQ' + PR)( P'R' + Q')$ simplifies to  (A) $PQ'$  (B) $PR'$ (C) $PQ'$  (D) $PR' + Q$  (GATE 2008)  Answer: (A) $PQ'$  Explanation:  $(P + Q')( PQ' + PR)( P'R' + Q')$  $= (PQ' + PR + PQ' + PQR)(P'R' + Q')$, since $AA = A$  $= PQ' + PQ'R + PQ' + PQ'R$, since $AA' = 0$  $= PQ' + PQ'R$  $= PQ'(1 + R)$  $= PQ'$  Previous Post Next Post

What is the minimum number of gates required to implement the Boolean function $(AB + C)$ if we have to use only 2-input NOR gates?  (A) 2  (B) 3  (C) 4  (D) 5  (GATE 2009)  Answer: (B) 3  Explanation:  $(A + BC) = (A + C)(B + C) = \big((A + C)' + (B + C)\big)'$  Therefore, two NOR gates is requiredto implement the given Boolean function.  Previous Post Next Post

Given $f_1$, $f_3$ and $f$ in canonical sum of products form (in decimal) for the circuit  $f_1 = \sum m(4, 5, 6, 7, 8)$,  $f_3 = \sum m(1, 6, 15)$,  $f = \sum m(1, 6, 8, 15)$,  then $f_2$ is  (A) $\sum m(4, 6)$  (B) $\sum m(4, 8)$  (C) $\sum m(6, 8)$  (D) $\sum m(4, 6, 8)$  (GATE 2008)  Answer: (C) $\sum m(6, 8)$  Explanantion:  $f = (f_1 \cap f_2) \cup f_3$  Check option (C):  $(f_1 \cap f_2) \cup f_3$  $= \big(\sum m(4, 5, 6, 7, 8) \cap \sum m(6, 8)\big) \cup \sum m(1, 6, 15)$  $= \sum m(6, 8) \cup \sum m(1, 6, 15)$  $= \sum m(1, 6, 8, 15)$   $= f$  Previous Post Next Post

The literal count of a Boolean expression is the sum of the number of times each literal appears in the expression. For example, the literal count of (xy + xz′) is 4. What are the minimum possible literal counts of the product-of-sum and sum-of-product representations, respectively, of the function given by the following Karnaugh map? Here, X denotes “don’t care”.  (A) (11, 9)  (B) (9, 13)  (C) (9, 10)  (D) (11, 11)  (GATE 2003)  Answer: (C) (9, 10)  Explanation:  Sum-of-product (SOP) = WY + W'Y' + Z'WX' + XYZ'  Therefore, literal count = 10  Product-of-sum (POS) = (Y' + Z')(W' + Z')(Z' + Y)(X + Z + W)   Therefore, linteral count = 9  Previous Post Next Post

The IEEE standard for floating-point numbers specifies how the single-precision (32-bit) and double-precision (64-bit) floating-point numbers are represented.  1. Single Precision:   The IEEE single-precision floating-point standard representation requires a 32-bit word. The first bit to the left is the sign bit , the next eight bits are the exponent bits , and the final 23 bits form the fraction part .  The value of a normalized number $= (-1)^s \times 1.m \times 2^{e^{-127}}$, where $s = 1$ fornegative number and $s = 0$ for the positive number, $m = $ mantisa and $e = $ exponent.  2. Double Precision:   The IEEE double-precision floating-point standard representation requires a 64-bit word. The first bit is the sign bit , the next eleven bits are the exponent bits , and the final 52 bits form the fraction part .   Example Problem:   The following is a scheme for floating-point number representation using 16 bits.  Bit Position 15 14...9 8...0 ...

In this tutorial, we will learn how to compute the difference between two binary numbers using 1's complement and 2's complement.  Let us consider two binary numbers $X$ and $Y$.  We want to compute $X - Y$ here.  Method 1: Using 1's complement  Step 1: Find 1's complement of $Y$.  Step 2: Add $X$ and $Y$.  Step 3: If there is a carry, then add this carry to the answer. If there is no carry, then find the 1's complement of the answer and place a negative sign in front of the answer.  Example 1: Compute $(101)_2 - (011)_2$ using 1's complement method.   Solution:  Here, $X = (101)_2$ and $Y = (011)_2$.  Step 1: 1's complement of $Y$ is $(100)_2$.  Step 2: $X + Y = (101)_2 + (100)_2 = (1 001)_2$.  Step 3: There is a carry of 1, so now we will add this carry to the answer.  Therefore, the final result is $(1)_2 + (001)_2 = (010)_2$.  Example 2: Compute $(011)_2 - (101)_2$ using 1's complement method.  Solution...

In a game, two players $X$ and $Y$ toss a coin alternately. Whosoever gets a 'head' first wins the game and the game is terminated. Assuming that player $X$ starts the game. The probability of player $X$ winning the game is  (A) $\dfrac{1}{3}$  (B) $\dfrac{1}{2}$  (C) $\dfrac{2}{3}$  (D) $\dfrac{2}{4}$  Answer: (C) $\dfrac{2}{3}$  Explanation:  Here, the probability of getting a 'head' is, $p = \dfrac{1}{2}$, and  the probability of getting a 'tail' is, $q = \dfrac{1}{2}$.  Therefore, the required probability is  $p + q^2p + q^4p + \cdots$  $= p(1 + q^2 + q^4 + \cdots)$  $= p \times \dfrac{1}{1 - q^2}$  $= \dfrac{1}{2} \times \dfrac{1}{1 - \dfrac{1}{4}}$  $= \dfrac{2}{3}$ 

For a random variable $X$ ($-\infty < X < \infty$) following normal distribution, the mean is $\mu = 100$. If the $P(X \geq 110)$, the find $P(90 \leq X \leq 110)$.  (A) $1 - 2\alpha$  (B) $1 - \alpha$  (C) $1 - \dfrac{\alpha}{2}$  (D) $2\alpha$  Answer: (A) $1 - 2\alpha$  Explanation:  Here, $X$ is a random variable that follows a normal distribution with mean $\mu = 100$.  Given, $P(X \geq 110) = \alpha$  Hence, $P(X \leq 90) = \alpha$  Therefore, $P(90 \leq X \leq 110) = 1 - 2\alpha$. 

A coin is tossed 4 times. What is the probability of getting heads exactly 3 times?  (A) $\dfrac{1}{4}$  (B) $\dfrac{3}{8}$  (C) $\dfrac{1}{2}$  (D) $\dfrac{3}{4}$  Answer: (A) $\dfrac{1}{4}$  Explanation:  Let $X$ be a random variable that denotes the number of heads.  Here, $X$ follows the binomial distribution with the parameters $p = \dfrac{1}{2}$ and $n = 4$.  Hence, $P(X = r) = ^nC_r \times p^r \times (1 - p)^{n - r}$, where $r = 1, \ldots, n$.  Therefore, the required probability is  $P(X = 3) = ^4C_3 \times (\dfrac{1}{2})^3 \times (1 - \dfrac{1}{2})^{4 - 3}$  $= 4 \times \dfrac{1}{8} \times \dfrac{1}{2}$  $= \dfrac{1}{4}$ 

A random variable is uniformly distributed over the interval 2 to 10. Its variance will be  (A) $\dfrac{16}{3}$  (B) 6  (C) $\dfrac{256}{9}$  (D) 36  Answer: (A) $\dfrac{16}{3}$  Explanation:  The expected value (i.e. the mean) of a uniform random variable $X$ is:  $E(X) = \dfrac{b + a}{2}$.  The variance of a uniform random variable $X$ is:  $Var(X) = \dfrac{(b - a)^2}{12}$.  Here, $a$ is the minimum value in the distribution, and $b$ is the maximum value.  For the given problem, $a = 2$ and $b = 12$.  Therefore, $Var(X) = \dfrac{(10 - 2)^2}{12} = \dfrac{16}{3}$. 

$X$ is a uniformly distributed random variable that takes values between zero and one. The value of $E( X^3)$ will be  (A) 0  (B) $\dfrac{1}{8}$  (C) $\dfrac{1}{4}$  (D) $\dfrac{1}{2}$  Answer: (C) $\dfrac{1}{4}$  Explanation:  Here, $X$ is a uniformly distributed random variable that takes values between 0 and 1.  Therefore, its p.d.f. is $f(x) = \dfrac{1}{1 - 0} = 1, \mbox{for } 0 < x < 1.$  Hence,  $E(X^3) = \int\limits_{0}^{1}x^3f(x)dx = \int\limits_{0}^{1}x^3dx = \dfrac{1}{4}$  Previous Post Next Post

An examination consists of two papers, Paper-1 and Paper-2. The probability of failing in Paper-1 is 0.3 and that in Paper-2 is 0.2. Given that a student has failed in Paper-2, the probability of failing in Paper-1 is 0.6. The probability of a student failing in both the papers is  (A) 0.5  (B) 0.18  (C) 0.12  (D) 0.06  Answer: (C) 0.12  Explanation:  Let $E_1$ and $E_2$ be the two events of failing in Paper-1 and Paper-2 respectively.  Given, $P(E_1) = 0.3$, $P(E_2) = 0.2$ and $P(E_1 | E_2) = 0.6$  Now, $P(E_1 | E_2) = \dfrac{P(E_1 \cap E_2)}{P(E_2)}$  $\Rightarrow 0.6 = \dfrac{P(E_1 \cap E_2)}{0.2}$  $\Rightarrow P(E_1 \cap E_2) = 0.12$, which is the required probability. 

If X is a continuous random variable whose probability density function is given by \[f(x) = \left\{ \begin{array}{ll} k(5x - 2x^2) & \mbox{if } 0 \leq x \leq 2 \\ 0 & \mbox{otherwise,} \end{array} \right.\] then $P(X > 1)$ is  (A) $\dfrac{3}{14}$  (B) $\dfrac{4}{5}$  (C) $\dfrac{14}{7}$  (D) $\dfrac{17}{28}$  Answer: (D) $\dfrac{17}{28}$  Explanation:  $\int\limits_{-\infty}^{+\infty}f(x)dx = 1$  $\Rightarrow \int\limits_{0}^{2}k(5x-2x^2)dx = 1$  $\Rightarrow k = \dfrac{3}{14}$  Now, $P(X > 1)$  $= \int\limits_{1}^{\infty}f(x)dx$  $= \int\limits_{1}^{2} \dfrac{3}{14}(5x - 2x^2)dx$  $= \dfrac{17}{28}$