CMI M.Sc. and Ph.D. Computer Science Mock Tests

**Step 1: Determine the elements of the relation $R$.**\nThe relation $R$ is defined as $R = \{(x, y) \in A \times B \mid x \text{ is even or } y = a\}$.\n\nFirst, let's list the elements of the Cartesian product $A \times B$:\n$A \times B = \{(1,a), (1,b), (1,c), (2,a), (2,b), (2,c), (3,a), (3,b), (3,c), (4,a), (4,b), (4,c)\}$.\n\nNow, we identify pairs $(x,y)$ from $A \times B$ that satisfy the condition ($x$ is even OR $y=a$):\n* Pairs where $x$ is even (i.e., $x \in \{2, 4\}$):\n $(2,a), (2,b), (2,c)$\n $(4,a), (4,b), (4,c)$\n* Pairs where $y = a$:\n $(1,a), (2,a), (3,a), (4,a)$\n\nCombining these sets and removing duplicates (e.g., $(2,a)$ and $(4,a)$ appear in both lists), we get the relation $R$:\n\n\n**Step 2: Evaluate each option.**\n\n* **Option 1: "$|R| = 8$"**\n By counting the distinct elements in $R$ identified in Step 1, we find that $R$ contains 8 elements. Thus, $|R| = 8$.\n Alternatively, using the Principle of Inclusion-Exclusion:\n Let $S_1 = \{(x,y) \in A \times B \mid x \text{ is even}\}$. There are 2 even numbers in $A$ (2 and 4) and 3 elements in $B$, so $|S_1| = 2 \times 3 = 6$.\n Let $S_2 = \{(x,y) \in A \times B \mid y = a\}$. There are 4 elements in $A$ and 1 element $a$ in $B$, so $|S_2| = 4 \times 1 = 4$.\n The intersection $S_1 \cap S_2 = \{(x,y) \in A \times B \mid x \text{ is even and } y = a\}$. These pairs are $(2,a)$ and $(4,a)$, so $|S_1 \cap S_2| = 2$.\n Therefore, $|R| = |S_1 \cup S_2| = |S_1| + |S_2| - |S_1 \cap S_2| = 6 + 4 - 2 = 8$.\n This statement is **true**.\n\n* **Option 2: "The range of $R$ is $B$."**\n The range of $R$, denoted $\operatorname{Ran}(R)$, is the set of all second elements of the ordered pairs in $R$. From the elements of $R$ determined in Step 1, the second elements are $a, b, c$.\n Thus, $\operatorname{Ran}(R) = \{a, b, c\}$.\n Given $B = \{a, b, c\}$, we see that $\operatorname{Ran}(R) = B$.\n This statement is **true**.\n\n* **Option 3: "$(3, b) \in R$"**\n For the pair $(3,b)$ to be in $R$, it must satisfy the condition: $3$ is even OR $b = a$.\n Neither $3$ is even (it's odd) nor $b = a$ (they are distinct elements). Since both parts of the 'OR' condition are false, the condition is false.\n Therefore, $(3, b) \notin R$.\n This statement is **false**.\n\n* **Option 4: "The codomain of $R$ is the set of all first elements of the ordered pairs in $R$."**\n According to the definition, the codomain of a relation $R$ from $A$ to $B$ is the set $B$. In this case, the codomain is $B = \{a, b, c\}$.\n The set of all first elements of the ordered pairs in $R$ is $\{1, 2, 3, 4\}$, which is the set $A$.\n Since $B \neq A$, the statement that the codomain of $R$ is the set of all first elements of the ordered pairs in $R$ is incorrect. It confuses the codomain with the domain (specifically, the set of first components that appear in the relation itself).\n This statement is **false**.\n\n**Conclusion:** The true statements are Option 1 and Option 2.

Let $D$ be the event that an item is defective, and $D^c$ be the event that an item is non-defective. Let $C_1^F$ be the event that Check 1 flags the item (i.e., it fails Check 1), and $C_1^P$ be the event that it passes Check 1. Let $C_2^F$ be the event that Check 2 flags the item (i.e., it fails Check 2), and $C_2^P$ be the event that it passes Check 2. We are given the following probabilities: $P(D) = 0.05 \implies P(D^c) = 1 - 0.05 = 0.95$ For Check 1: $P(C_1^F|D) = 0.9$ (defective item detected) $P(C_1^F|D^c) = 0.05$ (non-defective item incorrectly flagged) From these, we can infer: $P(C_1^P|D) = 1 - P(C_1^F|D) = 1 - 0.9 = 0.1$ $P(C_1^P|D^c) = 1 - P(C_1^F|D^c) = 1 - 0.05 = 0.95$ For Check 2: $P(C_2^F|D) = 0.8$ (defective item detected) $P(C_2^F|D^c) = 0.02$ (non-defective item incorrectly flagged) From these, we can infer: $P(C_2^P|D) = 1 - P(C_2^F|D) = 1 - 0.8 = 0.2$ $P(C_2^P|D^c) = 1 - P(C_2^F|D^c) = 1 - 0.02 = 0.98$ The outcomes of Check 1 and Check 2 are conditionally independent given the true state of the item. **1. Evaluate Option 1: The probability that an item is defective given it failed Check 1.** We need to calculate $P(D|C_1^F)$. Using Bayes' Theorem: First, calculate $P(C_1^F)$: Now, substitute into Bayes' Theorem: So, Option 1 is TRUE. **2. Evaluate Option 2: The probability that an item is defective given it failed Check 2.** We need to calculate $P(D|C_2^F)$. Using Bayes' Theorem: First, calculate $P(C_2^F)$: Now, substitute into Bayes' Theorem: So, Option 2 is TRUE. **3. Evaluate Option 3: The probability that an item is defective given it failed both Check 1 and Check 2 is less than $0.95$.** We need to calculate $P(D|C_1^F \cap C_2^F)$. Using Bayes' Theorem: Due to conditional independence: $P(C_1^F \cap C_2^F|D) = P(C_1^F|D)P(C_2^F|D) = (0.9)(0.8) = 0.72$ $P(C_1^F \cap C_2^F|D^c) = P(C_1^F|D^c)P(C_2^F|D^c) = (0.05)(0.02) = 0.001$ Now, calculate $P(C_1^F \cap C_2^F)$: Substitute into Bayes' Theorem: To compare with $0.95$, we calculate the decimal value: Since $0.974289 > 0.95$, the statement that the probability is less than $0.95$ is FALSE. **4. Evaluate Option 4: The probability that an item is non-defective given it passed both Check 1 and Check 2 is greater than $0.99$.** We need to calculate $P(D^c|C_1^P \cap C_2^P)$. Using Bayes' Theorem: Due to conditional independence: $P(C_1^P \cap C_2^P|D^c) = P(C_1^P|D^c)P(C_2^P|D^c) = (0.95)(0.98) = 0.931$ $P(C_1^P \cap C_2^P|D) = P(C_1^P|D)P(C_2^P|D) = (0.1)(0.2) = 0.02$ Now, calculate $P(C_1^P \cap C_2^P)$: Substitute into Bayes' Theorem: To compare with $0.99$, we calculate the decimal value: Since $0.9988706 > 0.99$, Option 4 is TRUE.

**1. Best-Case Analysis for BST Insertion:** * **Input Sequence:** The best-case performance for inserting $n$ distinct elements into an initially empty BST occurs when the elements are inserted in an order that keeps the tree as balanced as possible. This means inserting the median element of the sorted set first, then recursively inserting the medians of the left and right sub-problems. For example, if inserting elements from $1$ to $n$, the sequence would begin with $\lfloor n/2 \rfloor$, then $\lfloor n/4 \rfloor$, $\lfloor 3n/4 \rfloor$, and so on. This strategy ensures the tree maintains a height of $O(\log n)$. * **Total Time Complexity:** $O(n \log n)$ * **Justification:** In a perfectly balanced BST, the height of the tree is $O(\log n)$. Each insertion operation involves traversing a path from the root to a leaf node (or an empty slot where the new node will be placed). The length of this path (and thus the number of comparisons) is proportional to the current height of the tree. Since the tree remains balanced throughout the insertions, each of the $n$ insertions takes approximately $O(\log i)$ time, where $i$ is the number of nodes already in the tree. Summing these operations, the total number of comparisons for $n$ insertions is $\sum_{i=1}^{n} O(\log i) = O(n \log n)$. **2. Worst-Case Analysis for BST Insertion:** * **Input Sequence:** The worst-case performance occurs when the elements are inserted in a strictly increasing or strictly decreasing order. For example, inserting elements $1, 2, 3, \dots, n$ in that sequence, or $n, n-1, \dots, 1$. This causes the BST to degenerate into a skewed tree, essentially a linked list, where each node has only one child. * **Total Time Complexity:** $O(n^2)$ * **Justification:** When elements are inserted in a strictly sorted order, each new element is always placed as the child of the deepest node (e.g., always the right child for increasing order). The $i$-th element inserted will traverse a path of length $i-1$ (making $i$ comparisons) to find its position. For instance, the first element takes 1 comparison, the second takes 2, the third takes 3, and so on, up to $n$ comparisons for the $n$-th element. The total number of comparisons is the sum of an arithmetic series: $1 + 2 + \dots + n = \frac{n(n+1)}{2}$, which is $O(n^2)$. **3. Average-Case Analysis for BST Insertion:** * **Input Sequence:** The average-case performance is typically observed when the $n$ distinct elements are inserted in a **random permutation**. This means that any of the $n!$ possible orderings of the $n$ elements is equally likely to be the input sequence. * **Total Time Complexity:** $O(n \log n)$ * **Intuition:** While individual insertions can still take $O(n)$ time in a randomly built BST (e.g., if a few elements happen to form a short skewed path), the probability of the tree consistently degenerating into a worst-case (skewed) structure is very low for a truly random input sequence. On average, the randomness in the input order helps to distribute elements across the tree, preventing extreme skewness. This results in the tree's height growing proportionally to $\log n$. The expected number of comparisons for a single insertion into a randomly built BST of $i$ nodes is $O(\log i)$. Therefore, summing over $n$ insertions, the total expected number of comparisons is $O(n \log n)$. The average shape of a randomly built BST closely resembles that of a balanced tree.

To determine if a function is continuous at $x=0$, we must check three conditions: 1. $f(0)$ is defined. 2. $\lim_{x \to 0} f(x)$ exists. 3. $\lim_{x \to 0} f(x) = f(0)$. Let's analyze each function: **For $f(x) = \begin{cases} x^2 \cos\left(\frac{1}{x}\right) & x \neq 0 \\ 0 & x = 0 \end{cases}$** 1. $f(0) = 0$ (defined). 2. We need to evaluate $\lim_{x \to 0} x^2 \cos\left(\frac{1}{x}\right)$. We know that for $x \neq 0$, $-1 \le \cos\left(\frac{1}{x}\right) \le 1$. Multiplying by $x^2$ (which is non-negative), we get -x^2 \le x^2 \cos\left(\frac{1}{x} ight) \le x^2. Since $\lim_{x \to 0} (-x^2) = 0$ and $\lim_{x \to 0} x^2 = 0$, by the Squeeze Theorem, 3. Since $\lim_{x \to 0} f(x) = 0$ and $f(0) = 0$, the third condition is satisfied. Therefore, $f(x)$ is continuous at $x=0$. **For $g(x) = \begin{cases} \frac{\sin x}{|x|} & x \neq 0 \\ 1 & x = 0 \end{cases}$** 1. $g(0) = 1$ (defined). 2. We need to evaluate $\lim_{x \to 0} g(x)$. We consider left-hand and right-hand limits. For $x > 0$, $|x| = x$, so $g(x) = \frac{\sin x}{x}$. For $x < 0$, $|x| = -x$, so $g(x) = \frac{\sin x}{-x}$. Since the left-hand limit ($-1$) is not equal to the right-hand limit ($1$), $\lim_{x \to 0} g(x)$ does not exist. Therefore, $g(x)$ is discontinuous at $x=0$. **For $h(x) = \begin{cases} e^{1/x} & x \neq 0 \\ 0 & x = 0 \end{cases}$** 1. $h(0) = 0$ (defined). 2. We need to evaluate $\lim_{x \to 0} h(x)$. We consider left-hand and right-hand limits. As $x \to 0^+$, $1/x \to \infty$, so $e^{1/x} \to \infty$. As $x \to 0^-$, $1/x \to -\infty$, so $e^{1/x} \to 0$. Since the left-hand limit ($0$) is not equal to the right-hand limit ($\infty$), $\lim_{x \to 0} h(x)$ does not exist. Therefore, $h(x)$ is discontinuous at $x=0$. **For $k(x) = \lfloor x \rfloor \sin(\pi x)$** 1. $k(0) = \lfloor 0 \rfloor \sin(\pi \cdot 0) = 0 \cdot \sin(0) = 0 \cdot 0 = 0$ (defined). 2. We need to evaluate $\lim_{x \to 0} k(x)$. We consider left-hand and right-hand limits. For $x \in (-1, 0)$, $\lfloor x \rfloor = -1$. For $x \in (0, 1)$, $\lfloor x \rfloor = 0$. Since the left-hand limit ($0$) is equal to the right-hand limit ($0$), $\lim_{x \to 0} k(x)$ exists and is equal to $0$. 3. Since $\lim_{x \to 0} k(x) = 0$ and $k(0) = 0$, the third condition is satisfied. Therefore, $k(x)$ is continuous at $x=0$. **Conclusion:** Functions $f(x)$ and $k(x)$ are continuous at $x=0$.

Let $E$ be the event of an electrical defect and $M$ be the event of a mechanical defect. Let $T_E$, $T_M$, and $T_N$ be the events of the test indicating 'Electrical Issue', 'Mechanical Issue', and 'No Issue', respectively. Given probabilities: $P(E) = 0.02$ $P(M) = 0.03$ $E$ and $M$ are independent. First, calculate the probabilities of the four mutually exclusive and exhaustive defect states: 1. Probability of both defects ($E \cap M$): $P(E \cap M) = P(E)P(M) = 0.02 \times 0.03 = 0.0006$ 2. Probability of only an electrical defect ($E \cap M^c$): $P(E \cap M^c) = P(E)P(M^c) = P(E)(1 - P(M)) = 0.02 \times (1 - 0.03) = 0.02 \times 0.97 = 0.0194$ 3. Probability of only a mechanical defect ($E^c \cap M$): $P(E^c \cap M) = P(E^c)P(M) = (1 - P(E))P(M) = (1 - 0.02) \times 0.03 = 0.98 \times 0.03 = 0.0294$ 4. Probability of no defects ($E^c \cap M^c$): $P(E^c \cap M^c) = P(E^c)P(M^c) = (1 - P(E))(1 - P(M)) = 0.98 \times 0.97 = 0.9506$ Check sum: $0.0006 + 0.0194 + 0.0294 + 0.9506 = 1.0000$. Next, calculate the marginal probabilities of the test results using the Law of Total Probability: $P(T_X) = P(T_X | E \cap M^c)P(E \cap M^c) + P(T_X | E^c \cap M)P(E^c \cap M) + P(T_X | E \cap M)P(E \cap M) + P(T_X | E^c \cap M^c)P(E^c \cap M^c)$ * **$P(T_E)$:** $P(T_E) = (0.90)(0.0194) + (0.10)(0.0294) + (0.60)(0.0006) + (0.03)(0.9506)$ $P(T_E) = 0.01746 + 0.00294 + 0.00036 + 0.028518 = 0.049278$ * **$P(T_M)$:** $P(T_M) = (0.05)(0.0194) + (0.85)(0.0294) + (0.30)(0.0006) + (0.01)(0.9506)$ $P(T_M) = 0.00097 + 0.02499 + 0.00018 + 0.009506 = 0.035646$ * **$P(T_N)$:** $P(T_N) = (0.05)(0.0194) + (0.05)(0.0294) + (0.10)(0.0006) + (0.96)(0.9506)$ $P(T_N) = 0.00097 + 0.00147 + 0.00006 + 0.912576 = 0.915076$ Check sum: $P(T_E) + P(T_M) + P(T_N) = 0.049278 + 0.035646 + 0.915076 = 1.000000$. Now, evaluate each statement: **Option 0: The probability that the widget has an electrical defect, given the test indicated 'Electrical Issue', is approximately $0.362$.** We need to find $P(E | T_E)$. This is $P((E \cap M^c) \cup (E \cap M) | T_E)$. Using Bayes' Theorem: $P(E | T_E) = \frac{P(E \cap T_E)}{P(T_E)}$. $P(E \cap T_E) = P(T_E | E \cap M^c)P(E \cap M^c) + P(T_E | E \cap M)P(E \cap M)$ $P(E \cap T_E) = (0.90)(0.0194) + (0.60)(0.0006) = 0.01746 + 0.00036 = 0.01782$ $P(E | T_E) = \frac{0.01782}{0.049278} \approx 0.361623 \approx 0.362$. This statement is **True**. **Option 1: The probability that the widget has a mechanical defect, given the test indicated 'Mechanical Issue', is approximately $0.706$.** We need to find $P(M | T_M)$. This is $P((E^c \cap M) \cup (E \cap M) | T_M)$. Using Bayes' Theorem: $P(M | T_M) = \frac{P(M \cap T_M)}{P(T_M)}$. $P(M \cap T_M) = P(T_M | E^c \cap M)P(E^c \cap M) + P(T_M | E \cap M)P(E \cap M)$ $P(M \cap T_M) = (0.85)(0.0294) + (0.30)(0.0006) = 0.02499 + 0.00018 = 0.02517$ $P(M | T_M) = \frac{0.02517}{0.035646} \approx 0.706194 \approx 0.706$. This statement is **True**. **Option 2: The probability that the widget has no defects, given the test indicated 'No Issue', is approximately $0.990$.** We need to find $P(E^c \cap M^c | T_N)$. Using Bayes' Theorem: $P(E^c \cap M^c | T_N) = \frac{P(T_N | E^c \cap M^c)P(E^c \cap M^c)}{P(T_N)}$. $P(E^c \cap M^c | T_N) = \frac{(0.96)(0.9506)}{0.915076} = \frac{0.912576}{0.915076} \approx 0.997279 \approx 0.997$. The statement says $0.990$. This statement is **False**. **Option 3: The probability that the widget has both defects, given the test indicated 'Electrical Issue', is approximately $0.007$.** We need to find $P(E \cap M | T_E)$. Using Bayes' Theorem: $P(E \cap M | T_E) = \frac{P(T_E | E \cap M)P(E \cap M)}{P(T_E)}$. $P(E \cap M | T_E) = \frac{(0.60)(0.0006)}{0.049278} = \frac{0.00036}{0.049278} \approx 0.007305 \approx 0.007$. This statement is **True**. Therefore, statements 0, 1, and 3 are true.