Category: Discrete Mathematics Objective Questions

Discrete Mathematics Multiple Choice Questions on “Discrete Probability – Mean and Variance of Random Variables”.

1. Two t-shirts are drawn at random in succession without replacement from a drawer containing 5 red t-shirts and 8 white t-shirts. Find the probabilities of all the possible outcomes.
a) 1
b) 13
c) 40
d) 346

Answer: a
Clarification: Let X denote the number of red t-shirts in the outcome. Here, x₁ = 2, x₂ = 1, x₃ = 1, x₄ = 1, x₅ = 0. Probability of first t-shirt being red = (frac{5}{13}).
Probability of second t-shirt being red = (frac{4}{12}).
So: P(x₁) = (frac{5}{13} × frac{4}{12} = frac{20}{146}). Likewise, for the probability of red first followed by black is (frac{8}{12}) (as there are 8 red t-shirts still in the drawer and 12 t-shirts all together).
So, P(x₂) = (frac{5}{13} *frac{8}{12} = frac{40}{146}). Similarly for white then red: P(x₃) = (frac{8}{13} × frac{4}{12} = frac{32}{146}). Finally, for 2 black balls: P(x₄) = (frac{8}{13} × frac{7}{12} = frac{56}{146}). So, (frac{20}{146} + frac{40}{146} + frac{32}{146} + frac{40}{146} = 1). Hence, all the t-shirts have been found.

2. A jar of pickle is picked at random using a filling process in which an automatic machine is filling pickle jars with 2.5 kg of pickle in each jar. Due to few faults in the automatic process, the weight of a jar could vary from jar to jar in the range 1.7 kg to 2.9 kg excluding the latter. Let X denote the weight of a jar of pickle selected. Find the range of X.
a) 3.7 ≤ X < 3.9
b) 1.6 ≤ X < 3.2
c) 1.7 ≤ X < 2.9
d) 1 ≤ X < 5

Answer: c
Clarification: Possible outcomes should be 1.7 ≤ X < 2.9. That is the probable range of X for the answer.

3. A probability density function f(x) for the continuous random variable X is denoted as _______
a) ∫ f(x)dx = ∞, -1<=x<=1
b) ∫ f(x)dx = 1, -∞<=x<=∞
c) ∫ f(x)dx = 0, -∞<=x<=∞
d) ∫ f(x+2)dx = .5, -∞<=x<=∞

Answer: b
Clarification: A probability density function f(x) for the continuous random variable X is denoted as ∫ f(x)dx = 1, -∞<=x<=∞. The area under the curve between any two ordinates x = a and x = b is a probability that X lies between a and b. So, ∫f(x)dx = P(a≤X≤b).

4. Let X is denoted as the number of heads in three tosses of a coin. Determine the mean and variance for the random variable X.
a) 4.8
b) 6
c) 3.2
d) 1.5

Answer: d
Clarification: Let H represents a head and T be a tail. X denotes the number of heads in three tosses of a coin. X can take the value 0, 1, 2, 3. P(X = 0) = (frac{1}{8}), P(X = 1) = (frac{3}{8}), P(X = 2) = (frac{3}{8}), P(X = 3) = (frac{1}{8}). The probability distribution of X is E(X) = Σ_ix_ip_i = 1 × (frac{3}{8} + 2 × frac{3}{8} + 3 × frac{1}{8}) = 1.5. E(X₂) = (12 × frac{3}{8} + 22 × frac{3}{8} + 32 × frac{1}{8}) = 3. So, Variance of X = V(X) = E(X²) – [E(X)]² = 3 – 1.5 = 1.5.

5. A football player makes 75% of his 5-point shots and 25% his 7-point shots. Determine the expected value for a 7-point shot of the player.
a) 4.59
b) 12.35
c) 5.25
d) 42.8

Answer: c
Clarification: Multiply the outcome by its probability, so the expected value becomes 0.75 * 7 points = 5.25.

6. In a card game Reena wins 3 Rs. if she draws a king or a spade and 7 Rs. if a heart or a queen from an pack of 52 playing cards. If she pays a certain amount of money each time she will lose the game. What will be the amount so that the game will come out a fair game?
a) 15
b) 6
c) 23
d) 2

Answer: d
Clarification: We know that E(X) = ∑{x_i * P(xi)} = 3 * (frac{2}{13} + 7 * frac{2}{13} − x * frac{10}{13} = frac{20}{13} − frac{10x}{13}). Suppose the expected value should be 0 Rs. for the game to be fair. So (frac{20}{13} − frac{10x}{13}) = 0 ⇒ x=2. So she should pay Rs.2 for it to be a fair game.

7. A Random Variable X can take only two values, 4 and 5 such that P(4) = 0.32 and P(5) = 0.47. Determine the Variance of X.
a) 8.21
b) 12
c) 3.7
d) 4.8

Answer: c
Clarification: Expected Value: μ = E(X) = ∑x * P(x) = 4 × 0.32 + 5 × 0.47 = 3.63. Next find ∑x² * P(x): ∑x² * P(x) = 16 × 0.32 + 25 × 0.47 = 16.87. Therefore, Var(X) = ∑x²P(x) − μ² = 16.87 − 13.17 = 3.7.

8. A 6-sided die is biased. Now, the numbers one to four are equally likely to happen, but five and six is thrice as likely to land face up as each of the other numbers. If X is the number shown on the uppermost face, determine the expected value of X when 6 is shown on the uppermost face.
a) (frac{13}{4})
b) (frac{3}{5})
c) (frac{2}{7})
d) (frac{21}{87})

Answer: a
Clarification: Let P(1) = P(2) = P(3) = P(4) = p; P(5) = P(6) = 2p. We know that the sum of all probabilities must be 1 ⇒ p + p + p + p + 2p + 2p = 1
⇒ 8p = 1 ⇒ p = (frac{1}{8})
Expected Value:
μ = E(X) = ∑x * P(x) = (1 * frac{1}{8} + 2 * frac{1}{8} + 3 * frac{1}{8} + 4 * frac{1}{8} + 5 * frac{2}{8} + 6 * frac{2}{8} = frac{13}{4}).

9. A fair cubical die is thrown twice and their scores summed up. If the sum of the scores of upper side faces by throwing two times a die is an event. Find the Expected Value of that event.
a) 48
b) 76
c) 7
d) 132

Answer: c
Clarification: Sample space = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}.Suppose: P(2) = (frac{1}{36}), P(3) = (frac{2}{36}), P(4) = (frac{3}{36}), P(5) = (frac{4}{36}), P(6) = (frac{5}{36}), P(7) = (frac{6}{36}), P(8) = (frac{5}{36}), P(9) = (frac{4}{36}), P(10) = (frac{3}{36}), P(11) = (frac{2}{36}) and P(12) = (frac{1}{36}). Now, Expected Value:
μ = E(A) = ∑x * P(x) = (2 * frac{1}{36} + 3 * frac{2}{36} + 4 * frac{3}{36} + 5 * frac{4}{36} + 6 * frac{5}{36} )
(+ 7 * frac{6}{36} + 8 * frac{5}{36} + 9 * frac{4}{36} + 10 * frac{3}{36} + 11 * frac{2}{36} + 12 * frac{1}{36} = frac{252}{36}) = 7.

10. A random variable X can take only two values, 2 and 4 i.e., P(2) = 0.45 and P(4) = 0.97. What is the Expected value of X?
a) 3.8
b) 2.9
c) 4.78
d) 5.32

Answer: c
Clarification: We know that E(X) = ∑ x*P(x) = 2 × 0.45 + 4 × 0.97 = 4.78, where x={2,4}.

Tricky Discrete Mathematics Questions and Answers on “Complete and Connected Graphs”.

1. A bridge can not be a part of _______
a) a simple cycle
b) a tree
c) a clique with size ≥ 3 whose every edge is a bridge
d) a graph which contains cycles

Answer: a
Clarification: In a connected graph, a bridge is an edge whose removal disconnects the graph. In a cycle if we remove an edge, it will still be connected. So, bridge cannot be part of a cycle. A clique is any complete subgraph of a graph.

2. Any subset of edges that connects all the vertices and has minimum total weight, if all the edge weights of an undirected graph are positive is called _______
a) subgraph
b) tree
c) hamiltonian cycle
d) grid

Answer: b
Clarification: If all the edge weights of an undirected graph are positive, any subset of edges that connects all the vertices and has minimum total weight is termed as a tree. In this case, we need to have a minimum spanning tree need to be exact.

3. G is a simple undirected graph and some vertices of G are of odd degree. Add a node n to G and make it adjacent to each odd degree vertex of G. The resultant graph is ______
a) Complete bipartite graph
b) Hamiltonian cycle
c) Regular graph
d) Euler graph

Answer: d
Clarification: In any simple undirected graph, total degree of all vertices is even (since each edge contributes 2 degrees). So number of vertices having odd degrees must be even, otherwise, their sum would have been odd, making total degree also odd. Now single vertex n is connected to all these even number of vertices (which have odd degrees). So, degree of n is also even. Moreover, now degree of all vertices which are connected to v is increased by 1, hence earlier vertices which had odd degree now have even degree. So now, all vertices in the graph have even degree, which is necessary and sufficient condition for euler graph.

4. Let G be a directed graph whose vertex set is the set of numbers from 1 to 50. There is an edge from a vertex i to a vertex j if and only if either j = i + 1 or j = 3i. Calculate the minimum number of edges in a path in G from vertex 1 to vertex 50.
a) 98
b) 13
c) 6
d) 34

Answer: c
Clarification: Edge set consists of edges from i to j using either 1) j = i+1 OR 2) j=3i. The trick to solving this question is to think in a reverse way. Instead of finding a path from 1 to 50, try to find a path from 100 to 1. The edge sequence with the minimum number of edges is 1 – 3 – 9 – 10 – 11 – 33 which consists of 6 edges.

5. What is the number of vertices in an undirected connected graph with 39 edges, 7 vertices of degree 2, 2 vertices of degree 5 and remaining of degree 6?
a) 11
b) 14
c) 18
d) 19

Answer: c
Clarification: We know that, sum of degree of all the vertices = 2 * number of edges
2*7 + 5*2 + 6*x = 39*2
x=9
Number of vertices = 7 + 2 + 9 = 18.

6. ______ is the maximum number of edges in an acyclic undirected graph with k vertices.
a) k-1
b) k²
c) 2k+3
d) k³+4

Answer: a
Clarification: This is possible with spanning trees since, a spanning tree with k nodes has k – 1 edges.

7. The minimum number of edges in a connected cyclic graph on n vertices is _____________
a) n – 1
b) n
c) 2n+3
d) n+1

Answer: b
Clarification: For making a cyclic graph, the minimum number of edges have to be equal to the number of vertices. SO, the answer should be n minimum edges.

8. The maximum number of edges in a 8-node undirected graph without self loops is ____________
a) 45
b) 61
c) 28
d) 17

Answer: c
Clarification: In a graph of n vertices we can draw an edge from a vertex to n-1 vertex we will do it for n vertices and so total number of edges is n*(n-1). Now each edge is counted twice so the required maximum number of edges is n*(n-1)/2. Hence, 8*(8-1)/2 = 28 edges.

9. Let G be an arbitrary graph with v nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie down between _____ and _____
a) n-1 and n+1
b) v and k
c) k+1 and v-k
d) k-1 and v-1

Answer: d
Clarification: If a vertex is removed from the graph, lower bound: number of components decreased by one = k-1 (remove an isolated vertex which was a component) and upper bound: number of components = v-1 (consider a vertex connected to all other vertices in a component as in a star and all other vertices outside this component being isolated. Now, removing the considered vertex makes all other (v-1) vertices isolated making (v-1) components.

10. The 2ⁿ vertices of a graph G corresponds to all subsets of a set of size n, for n>=4. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.
The number of connected components in G can be ___________
a) n+2
b) 3^n/2
c) n²
d) 2ⁿ

Answer: b
Clarification: n+1(subsets of size < 2 are all disconnected) (subsets of size >= 2 are all connected)+1(subset of size >= 2 are all connected)=n+2 is the number of connected components in G.

Discrete Mathematics Multiple Choice Questions on “Modeling Computations – Finite-State Automation”.

1. How many states are there in combinatorial FSM?
a) 86
b) 2¹⁹
c) 1
d) 132

Answer: c
Clarification: As an FSM’s memory is limited by the number of states, it cannot perform the computational tasks that a Turing machine can do. A “Combinatorial FSM” is defined as a finite state machine with only one state and it allows actions based upon transition into a state.

2. Which of the following algorithms transforms any NFA into its identical DFA?
a) Minimal set construction
b) Dynamic programming
c) Powerset construction
d) Huffman coding

Answer: b
Clarification: The powerset construction algorithm is a powerful algorithm that can transform any non-deterministic automaton into a more complex deterministic automaton with identical functionality.

3. Which of the following is not a member of the set of a deterministic finite state machine?
a) state-transition function
b) initial state
c) input symbols
d) stack

Answer: b
Clarification: A deterministic finite state machine or acceptor deterministic finite state machine is a quintuple (Σ, G, s1, δ, F), where: Σ is the input alphabet (a finite, non-empty set of symbols), G is a finite, non-empty set of states, s1 is an initial state, an element of S, δ is the state-transition function: δ: G × Σ → G.

4. In system engineering which of the following methods bridges the gap between the two ends of system development?
a) ASM method
b) VSM method
c) Factor method
d) FSM method

Answer: a
Clarification: An abstract state machine (ASM) has its operations on states that are arbitrary data structures as well as it can bridge the gap between the two ends of the system development. This method builds upon three basic concepts such as ASM, ground model and refinement.

5. Optimisation of an FSM machine can be done by ________
a) Naive-bias algorithm
b) Huffman encoding scheme
c) Pirate-plot algorithm
d) Hopcroft minimization algorithm

Answer: b
Clarification: The job of fastest known algorithm, hopcroft minimization algorithm is to optimize and FSM system that means finding a machine with the minimum number of states which can have the same function to perform. Acyclic FSAs can be minimized in linear time.

6. A deterministic automaton system can have ______ transition for a given state of an input symbol.
a) exactly one
b) more than one
c) no transition
d) 2n transition

Answer: a
Clarification: In a deterministic automaton, for each possible input every state has exactly one transition. In a non-deterministic automaton, an input can have one, more than one, or no transition for a given state. In the study of computation, a transition system is used and it can be made of states and transitions between states, which may be labeled with labels chosen from a set.

7. Which of the following techniques refer to the equivalence of DFA and N-DFA automata?
a) subset construction
b) superset construction
c) powerset construction
d) finite field construction

Answer: b
Clarification: For every N-DFA there is a corresponding DFA for every N-DFA, and the basic technique is described as subset construction because each state in the DFA corresponds to some subset of states of the NDFA.

8. Equivalence of automata states that ____________
a) two automata accept the same set of input strings
b) two automata have same set of states
c) two automata does not contain initial input symbols
d) two automata share equal transition function

Answer: a
Clarification: The formal definition is if two automata J and K are equivalent then if there is a path from the start state of J to a final state of J and there is a path from the start state of k to a final state of K as well as if there is a path from the start state of K to a final state of K, where there is a path from the start state of J to a final state of J. Two automata J and K are said to be equivalent if both automata accept exactly the same set of input strings.

9. In the operating system, newly started processes can have a start in the _________
a) Blocked state
b) Running sate
c) Ready state
d) Exit state

Answer: c
Clarification: In the behaviour of the processes, newly started processes start their execution in a Ready state and have to wait until the OS scheduler assigns a CPU to them. At that moment, the process starts running and it stays in this state until either the scheduler decides to take back the CPU (as a “time slice” has expired).

10. In lexical analysis of a compiler______ is used.
a) DFA
b) NDFA
c) NFA
d) Turing machine

Answer: a
Clarification: A Deterministic Finite automaton system is used in the lexical analysis of the compiler.

Discrete Mathematics Multiple Choice Questions on “Types of Set”.

1. {x: x is an integer neither positive nor negative} is ________
a) Empty set
b) Non-empty set
c) Finite set
d) Non- empty and Finite set

Answer: d
Clarification: Set = {0} non-empty and finite set.

2. {x: x is a real number between 1 and 2} is an ________
a) Infinite set
b) Finite set
c) Empty set
d) None of the mentioned

Answer: a
Clarification: It is an infinite set as there are infinitely many real number between any two different real numbers.

3. Write set {1, 5, 15, 25,…} in set-builder form.
a) {x: either x=1 or x=5n, where n is a real number}
b) {x: either x=1 or x=5n, where n is a integer}
c) {x: either x=1 or x=5n, where n is an odd natural number}
d) {x: x=5n, where n is a natural number}

Answer: c
Clarification: Set should include 1 or an odd multiple of 5.

4. Express {x: x= n/ (n+1), n is a natural number less than 7} in roster form.
a) {¹⁄₂, ²⁄₃, ⁴⁄₅, ⁶⁄₇}
b) {¹⁄₂, ²⁄₃, ³⁄₄, ⁴⁄₅, ⁵⁄₆, ⁶⁄₇, ⁷⁄₈}
c) {¹⁄₂, ²⁄₃, ³⁄₄, ⁴⁄₅, ⁵⁄₆, ⁶⁄₇}
d) Infinite set

Answer: c
Clarification: n/(n+1) = 1/(1+1) = ¹⁄₂ and n>7.

5. Number of power set of {a, b}, where a and b are distinct elements.
a) 3
b) 4
c) 2
d) 5

Answer: b
Clarification: Power set of {a, b} = {∅, {a, b}, {a}, {b}}.

6. Which of the following is subset of set {1, 2, 3, 4}?
a) {1, 2}
b) {1, 2, 3}
c) {1}
d) All of the mentioned

Answer: d
Clarification: There are total 16 subsets.

7. A = {∅,{∅},2,{2,∅},3}, which of the following is true?
a) {{∅,{∅}} ∈ A
b) {2} ∈ A
c) ∅ ⊂ A
d) 3 ⊂ A

Answer: c
Clarification: Empty set is a subset of every set.

8. Subset of the set A= { } is?
a) A
b) {}
c) ∅
d) All of the mentioned

Answer: d
Clarification: Every set is subset of itself and Empty set is subset of each set.

9. {x: x ∈ N and x is prime} then it is ________
a) Infinite set
b) Finite set
c) Empty set
d) Not a set

Answer: a
Clarification: There is no extreme prime, number of primes is infinite.

10. Convert set {x: x is a positive prime number which divides 72} in roster form.
a) {2, 3, 5}
b) {2, 3, 6}
c) {2, 3}
d) {∅}

Answer: c
Clarification: 2 and 3 are the divisors of 72 which are prime.

Discrete Mathematics Multiple Choice Questions on “Special Sequences”.

1. Let the sequence be 1×2, 3×2², 5×2³, 7×2⁴, 9×2⁵……… then this sequence is _________
a) An arithmetic sequence
b) A geometic progression
c) Arithmetico-geometric progression
d) None of the mentioned

Answer: c
Clarification: If a₁, a₂……… are in AP and b₁, b₂………. are in GP then a₂b₂, a₂b₂,……… are in AGP.

2. Let the sequence be 1×2, 3×2², 5×2³, 7×2⁴, 9×2⁵……… then the next term of this AGP is given by _________
a) 10×26
b) 10×27
c) 11×26
d) None of the mentioned

Answer: c
Clarification: Since here a₁, a₂……… are in AP and b₁, b₂………. are in GP then a₂b₂, a₂b₂,……… are in AGP thus a_n = 11 and b_n = 2⁶.

3. The sum of the first n natural numbers is given by _________
a) n(n+1)/2
b) n(n-1)/2
c) n²(n+1)/2
d) None of the mentioned

Answer: a
Clarification: 1 + 2 + 3 + 4 +……n = (n/2)(1 + n) Since this is AP.

4. The sum of square of the first n natural numbers is given by _________
a) n(n+1)(2n+1)/6
b) n(n-1)/2(2n+1)
c) n²(n+1)(2n+1)/6
d) None of the mentioned

Answer: a
Clarification: 1² + 2² + 3² + 4² +……n² = n(1+n)(2n+1)/6.

5. The sum of cubes of the first n natural numbers is given by _________
a) {n(n+1)/2}²
b) {n(n-1)/2}²
c) {n2(n+1)/2}²
d) None of the mentioned

Answer: a
Clarification: 1³ + 2³ + 3³ + 4³ +……+ n³ = {n(n+1)/2}².

6. The series 1, 1, 1, 1, 1…….. is not an AGP.
a) True
b) False

Answer: b
Clarification: Since 1, 1, 1, 1, 1…….. is in Ap and in Gp as well, Therefore the given sequence is also an AGP.

7. If in an AGP the common ratio of GP is 1 then that sequence becomes an AP sequence.
a) True
b) False

Answer: a
Clarification: In AGP sequence if r = 1, then terms are ab, (a+d)b, (a+2d)b…. and so on thus it is AP with common differnce bd.

8. The sequence 1, 1, 1, 1, 1…. is?
a) Absolutely summable
b) Is not absolutely summable
c) Can’t say
d) None of the mentioned

Answer: b
Clarification: For limit n tending to infinity the sum also tends to infinity and thus it is not summable.

9. Which of the following is a Triangular number series?
a) 1, 3, 6, 9, 12, 15…..
b) 1, 3, 6, 10, 15, 21……
c) 1, 6, 12, 18, 24…..
d) none of the mentioned

Answer: b
Clarification: In triangular number sequence ith term is previous term+i, with first term as 1.

10. Which of the following is a fibonacci series?
a) 0, 1, 2, 3, 4…….
b) 0, 1, 1, 2, 3, 5……
c) 10, 12, 14, 16…….
d) none of the mentioned

Answer: b
Clarification: Fibonacci series is formed by adding previous two term starting from 0 and 1.

Discrete Mathematics online quiz on “Number Theory – Quadratic Residue and Pseudo Prime”.

1. If there exist an integer x such that x² ≡ q (mod n). then q is called ______________
a) Quadratic Residue
b) Linear Residue
c) Pseudoprime
d) None of the mentioned

Answer: a
Clarification: q is called quadratic residue if it is congruent to a perfect square modulo n.

2. If there exist no integer x such that x² ≡ q (mod n). then q is called __________
a) Quadratic Residue
b) Quadratic Nonresidue
c) Pseudoprime
d) None of the mentioned

Answer: b
Clarification: q is called quadratic nonresidue if it is not congurent to a perfect square modulo n.

3. The Fermat’s little theorem for odd prime p and coprime number a is?
a) a^p-1 ≡ 1 (mod p)
b) a^p-1 ≡ 7 (mod p)
c) a^p(2)-1 ≡ 1 (mod p)
d) none of the mentioned

Answer: a
Clarification: According to Fermat’s little theorem a^p-1 ≡ 1 (mod p).

4. 5 is quardratic non-residue of 7.
a) True
b) False

Answer: a
Clarification: Since there exists no number which gives 5 modulo 7 when squared.

5. 4 is quardratic residue of 7.
a) True
b) False

Answer: a
Clarification: Since 25 ≡ 4(mod)7, 4 is quardratic residue of 7.

6. 8 is quardratic residue of 17.
a) True
b) False

Answer: a
Clarification: Since 25 ≡ 8(mod)17.

7. 8 is quardratic residue of 11.
a) True
b) False

Answer: b
Clarification: Since x² ≡ 8(mod)17 has no solutions.

8. Which of the following is a quardratic residue of 11?
a) 4
b) 5
c) 9
d) All of the mentioned

Answer: d
Clarification: Since 4, 16, 32 satisfies the criteria, all are quardratic residue of 11.

9. What is pseudo prime number?
a) is a probable prime and is not a prime number
b) is a prime number
c) does not share any property with prime number
d) none of the mentioned

Answer: a
Clarification: A pseudo prime number is an integer that shares a property common to all prime number and is not a prime number.

10. Pseudo prime are classified based on property which they satisfy, which of the following are classes of pseudoprimes?
a) Fermat pseudoprime
b) Fibonacci pseudoprime
c) Euler pseudoprime
d) All of the mentioned

Answer: d
Clarification: Fermat pseudoprime, Fibonacci pseudoprime, Euler pseudoprime are different classes of pseudoprimes.