# Discrete Mathematics

 Question 1
In a directed acyclic graph with a source vertex s, the quality-score of a directed path is defined to be the product of the weights of the edges on the path. Further, for a vertex v other than s, the quality-score of v is defined to be the maximum among the quality-scores of all the paths from s to v. The quality-score of s is assumed to be 1.

The sum of the quality-scores of all vertices on the graph shown above is ______
 A 929 B 254 C 639 D 879
GATE CSE 2021 SET-2      Graph Theory
Question 1 Explanation:
 Question 2
Let S be a set of consisting of 10 elements. The number of tuples of the form (A,B) such that A and B are subsets of S, and $A\subseteq B$ is _______
 A 49049 B 59049 C 3524 D 854
GATE CSE 2021 SET-2      Set Theory
Question 2 Explanation:
 Question 3
Consider the following directed graph:

Which of the following is/are correct about the graph?
[MSQ]
 A The graph does not have a topological order B A depth-first traversal starting at vertex S classifies three directed edges as back edges C The graph does not have a strongly connected component D For each pair of vertices u and v, there is a directed path from u to v
GATE CSE 2021 SET-2      Graph Theory
Question 3 Explanation:
 Question 4
A bag has $r$ red balls and $b$ black balls. All balls are identical except for their colours. In a trial, a ball is randomly drawn from the bag, its colour is noted and the ball is placed back into the bag along with another ball of the same colour. Note that the number of balls in the bag will increase by one, after the trial. A sequence of four such trials is conducted. Which one of the following choices gives the probability of drawing a red ball in the fourth trial?
 A $\dfrac{r}{r+b}$ B $\dfrac{r}{r+b+3}$ C $\dfrac{r+3}{r+b+3}$ D $\left( \dfrac{r}{r+b} \right) \left ( \dfrac{r+1}{r+b+1} \right) \left( \dfrac{r+2}{r+b+2} \right) \left( \dfrac{r+3}{r+b+3} \right)$
GATE CSE 2021 SET-2      Probability Theory
Question 4 Explanation:
 Question 5
In an examination, a student can choose the order in which two questions (QuesA and QuesB) must be attempted.

If the first question is answered wrong, the student gets zero marks.
If the first question is answered correctly and the second question is not answered correctly, the student gets the marks only for the first question.
If both the questions are answered correctly, the student gets the sum of the marks of the two questions.

The following table shows the probability of correctly answering a question and the marks of the question respectively.

$\begin{array}{c|c|c} \text{question} & \text{probabiloty of answering correctly} & \text{marks} \\ \hline \textsf{QuesA} & 0.8 & 10 \\ \textsf{QuesB} & 0.5 & 20 \end{array}$

Assuming that the student always wants to maximize her expected marks in the examination, in which order should she attempt the questions and what is the expected marks for that order (assume that the questions are independent)?
 A First QuesA and then QuesB. Expected marks 14. B First QuesB and then QuesA. Expected marks 14. C First QuesB and then QuesA. Expected marks 22. D First QuesA and then QuesB. Expected marks 16.
GATE CSE 2021 SET-2      Probability Theory
Question 5 Explanation:
 Question 6
Suppose that $f: \mathbb{R} \rightarrow \mathbb{R}$ is a continuous function on the interval [-3,3] and a differentiable function in the interval (-3,3) such that for every $x$ in the interval, $f'(x) \leq 2$. If $f(-3) =7$, then $f(3)$ is at most __________
 A 19 B 32 C 11 D 54
GATE CSE 2021 SET-2      Functions
Question 6 Explanation:
 Question 7
For a given biased coin, the probability that the outcome of a toss is a head is 0.4. This coin is tossed 1,000 times. Let X denote the random variable whose value is the number of times that head appeared in these 1,000 tosses. The standard deviation of X (rounded to 2 decimal place) is ________
 A 21.8 B 15.5 C 8.2 D 28.4
GATE CSE 2021 SET-2      Probability Theory
Question 7 Explanation:
 Question 8
Choose the correct choice(s) regarding the following proportional logic assertion S:

$S: (( P \wedge Q) \rightarrow R) \rightarrow (( P \wedge Q) \rightarrow (Q \rightarrow R))$
[MSQ]
 A S is neither a tautology nor a contradiction B S is a tautology C S is a contradiction D The antecedent of S is logically equivalent to the consequent of S
GATE CSE 2021 SET-2      Propositional Logic
Question 8 Explanation:
 Question 9
Consider the following sets, where $n\geq 2$:

S1: Set of all nxn matrices with entries from the set $\{a, b, c\}$
S2: Set of all functions from the set$\{0,1,2,...,n^2-1\}$ to the set $\{0, 1, 2 \}$

Which of the following choice(s) is/are correct?
[MSQ]
 A There does not exist a bijection from S1 to S2 B There exists a surjection from S1 to S2 C There exists a bijection from S1 to S2 D There does not exist an injection from S1 to S2
GATE CSE 2021 SET-2      Functions
Question 9 Explanation:
 Question 10
A sender (S) transmits a signal, which can be one of the two kinds: H and L with probabilities 0.1 and 0.9 respectively, to a receiver (R)
In the graph below, the weight of edge $(u,v)$ is the probability of receiving $v$ when $u$ is transmitted, where $u,v\in\{H,L\}$. For example, the probability that the received signal is $L$ given the transmitted signal was $H$, is 0.7.

If the received signal is $H$, the probability that the transmitted signal was $H$ (rounded to 2 decimal places) is __________.
 A 0.02 B 0.08 C 0.04 D 0.01
GATE CSE 2021 SET-1      Probability Theory
Question 10 Explanation:

There are 10 questions to complete.