250+ TOP MCQs on Permutation Groups and Answers

Discrete Mathematics Multiple Choice Questions on “Permutation Groups”.

1. Consider an integer 23 such that 23 >= 3p for a 2p-cycle in a permutation group, then p is ___________
a) odd prime
b) even prime
c) rational number
d) negative prime

Answer: a
Clarification: Let n an integer such that n>=3p and m is a 2p-cycle in the permutation group, then p is an odd prime.

2. Suppose Km={P∈Sm|, |P| is odd prime}. Determine the set for which m≥3 Km a subgroup of Sm.
a) {3, 5, 7, 11, 13, …}
b) {-14, -8, -3, 0, 3, 8, 14}
c) {2, 4, 6, 8, 10, 12}
d) {12, 25, 56, 78, 134,…}

Answer: a
Clarification: Since Km is a subset of Sm, then the set will be {3, 5, 7, 11, 13, …}.

3. The dihedral group having order 6 can have degree _____________
a) 3
b) 26
c) 326
d) 208

Answer: a
Clarification: A symmetric group on a set of three elements is said to be the group of all permutations of a three-element set. It is a dihedral group of order six having degree three.

4. Let (z, *) is a group with x*y=x+y-2 then inverse of x is ___________
a) -(x+4)
b) (x2+6)
c) (x+y)/5
d) (3y+4x2)

Answer: a
Clarification: Let, Identity element I, x*I = I*x = x ⇒ x = x + I – 2 ⇒ I = 2. Inverse of x is x-1
Now, x*x-1 = I
⇒ x + x-1 – 2 = 2
⇒ x-1 = -(x+4).

5. Let X be a n-square matrix such that Y = X + 8I. Which of the following property will exist?
a) idempotent
b) Y transpose is nilpotent
c) X nilpotent
d) Y inverse

Answer: b
Clarification: Suppose, we have a matrix
(a=begin{bmatrix}
1 & 0\
2 & 1\
end{bmatrix} )
then Y2 will not resulting in Y, hence it is not idempotent, Y2 is not 0 and so it is not nilpotent. But, as Y is a square matrix, by the property inverse will exist in this case.

6. Suppose, M is a lower triangular matrix with all diagonal entries zero. The resultant matrix of M+I will be ___________
a) idempotent
b) singular
c) nilpotent
d) inverse

Answer: b
Clarification: Since, M is a lower triangular matrix with diagonal elements zero, then we add I and it will result in a lower triangular matrix with all diagonal entries 1. Thus, all eigenvalues M+I are non zero (eigenvalues of triangular matrix is the diagonal elements). So, determinant will never be zero. Hence, the matrix can have inverse property.

7. If Y98 (a raised to the power of 5) = 0 and Y is a 97-square matrix. Determine the value of Y97.
a) I+Y
b) -Y+3
c) 0
d) Y2

Answer: c
Clarification: Question does not provide any notion of existing an inverse property or related to rank matrix. Hence, by considering zero matrix as Y and that satisfy all the constraints.

8. If 54th row of a 67th row matrix is linearly independent with each other then find the rank of the matrix.
a) 61
b) 54
c) 187
d) 32

Answer: b
Clarification: If kth row of a matrix with nth row is linearly independent then the rank of that matrix is k. If we take the transpose of a matrix the rank does not change. Hence, the answer is 54 in this case.

9. Let M be an 4×4 matrix with real entries such that Mk=0, for some k≥1. Find the determinant value of (I+M), where, I be the 4 x 4 identity matrix.
a) 72
b) 1
c) 4
d) 36

Answer: b
Clarification: By cayley hamilton theorem, M4 = 0. So, characteristic equation should be λ*4=0 and after solving we get 0 for every eigen value. Eigen values of (I+M) = Individual Eigen value of 1+m. So all the eigen values of (I+M) are 1 and Det(I+A) = 1.

10. Suppose (2, 5, 8, 4) and (3, 6) are the two permutation groups that form cycles. What type of permutation is this?
a) odd
b) even
c) acyclic
d) prime

Answer: b
Clarification: There are four permutations (2, 5), (2, 8), (2, 4) and (3, 6) and so it is an even permutation.

250+ TOP MCQs on Logics and Proofs – De-Morgan’s Laws and Answers

Discrete Mathematics Multiple Choice Questions on “Logics and Proofs – De-Morgan’s Laws”.

1. Which of the following statements is the negation of the statements “4 is odd or -9 is positive”?
a) 4 is even or -9 is not negative
b) 4 is odd or -9 is not negative
c) 4 is even and -9 is negative
d) 4 is odd and -9 is not negative

Answer: c
Clarification: Using De Morgan’s Law ~(A V B) ↔ ~A ∧ ~B.

2. Which of the following represents: ~A (negation of A) if A stands for “I like badminton but hate maths”?
a) I hate badminton and maths
b) I do not like badminton or maths
c) I dislike badminton but love maths
d) I hate badminton or like maths

Answer: d
Clarification: De Morgan’s Law ~ (A ∧ B) ↔ ~A V ~B.

3. The compound statement A v ~(A ∧ B).
a) True
b) False

Answer: a
Clarification: Applying De-Morgan’s law we get A v ~ A Ξ Tautology.

4. Which of the following is De-Morgan’s law?
a) P ∧ (Q v R) Ξ (P ∧ Q) v (P ∧ R)
b) ~(P ∧ R) Ξ ~P v ~R, ~(P v R) Ξ ~P ∧ ~R
c) P v ~P Ξ True, P ∧ ~P Ξ False
d) None of the mentioned

Answer: b
Clarification: Definition of De–Morgan’s Law.

5. What is the dual of (A ∧ B) v (C ∧ D)?
a) (A V B) v (C v D)
b) (A V B) ^ (C v D)
c) (A V B) v (C ∧ D)
d) (A ∧ B) v (C v D)

Answer: b
Clarification: In dual ∧ is replaced by v and vice – versa.

6. ~ A v ~ B is logically equivalent to?
a) ~ A → ~ B
b) ~ A ∧ ~ B
c) A → ~B
d) B V A

Answer: c
Clarification: By identity A → B Ξ ~A V B.

7. Negation of statement (A ∧ B) → (B ∧ C) is _____________
a) (A ∧ B) →(~B ∧ ~C)
b) ~(A ∧ B) v ( B v C)
c) ~(A →B) →(~B ∧ C)
d) None of the mentioned

Answer: a
Clarification: ~(A →B) Ξ A ∧ ~B using this we can easily fetch the answer.

8. Which of the following satisfies commutative law?
a) ∧
b) v
c) ↔
d) All of the mentioned

Answer: d
Clarification: All of them satisfies commutative law.

9. If the truth value of A v B is true, then truth value of ~A ∧ B can be ___________
a) True if A is false
b) False if A is false
c) False if B is true and A is false
d) None of the mentioned

Answer: a
Clarification: If A is false then both the condition are obeyed.

10. If P is always against the testimony of Q, then the compound statement P→(P v ~Q) is a __________
a) Tautology
b) Contradiction
c) Contingency
d) None of the mentioned

Answer: a
Clarification: Since either hypothesis is false or both (hypothesis as well as conclusion) are true.

250+ TOP MCQs on The Growth of Functions and Answers

Discrete Mathematics Multiple Choice s on “Growth of Functions”.

1. If f(x) = (x3 – 1) / (3x + 1) then f(x) is?
a) O(x2)
b) O(x)
c) O(x2 / 3)
d) O(1)

Answer: a
Clarification: 0 < (x3 – 1) / (3x + 1) 2.

2. If f(x) = 3x2 + x3logx, then f(x) is?
a) O(x2)
b) O(x3)
c) O(x)
d) O(1)

Answer: b
Clarification: 0 < 3x2 < x3, it follows that 0 < 3x2 + x3logx < x3. Consequently, f(x) = O(x3).

3. The big-O notation for f(n) = (nlogn + n2)(n3 + 2) is?
a) O(n2)
b) O(3n)
c) O(n4)
d) O(n5)

Answer: d
Clarification: 0 < n3 + 2 < n3, it follows that (nlogn + n2)(n3 + 2) is less than equal to n5.

4. The big-theta notation for function f(n) = 2n3 + n – 1 is?
a) n
b) n2
c) n3
d) n4

Answer: c
Clarification: 2n3 + n – 1 is less than equal to n3.

5. The big-theta notation for f(n) = nlog(n2 + 1) + n2logn is?
a) n2logn
b) n2
c) logn
d) nlog(n2)

Answer: a
Clarification: n2logn < n3, it follows that nlog(n2 + 1) + n2logn is less than n3 and greater than n2logn.

5. The big-omega notation for f(x, y) = x5y3 + x4y4 + x3y5 is?
a) x5y3
b) x5y5
c) x3y3
d) x4y4

Answer: c
Clarification: x5y3, x4y4 and x3y5 is greater than or equal to x3y3.

6. If f1(x) is O(g(x)) and f2(x) is o(g(x)), then f1(x) + f2(x) is?
a) O(g(x))
b) o(g(x))
c) O(g(x)) + o(g(x))
d) None of the mentioned

Answer: a
Clarification: f2(x) is less than O(g(x)). So, f1(x) + f2(x) upper bound is O(g(x)).

7. The little-o notation for f(x) = xlogx is?
a) x
b) x3
c) x2
d) xlogx

Answer: c
Clarification: Find the limit for xlogx / x2 as x tends to infinity.

8. The big-O notation for f(n) = 2log(n!) + (n2 + 1)logn is?
a) n
b) n2
c) nlogn
d) n2logn

Answer: d
Clarification: log(n!) < n2logn, it follows that 2log(n!) + (n2 + 1)logn is less than or equal n2logn.

9. The big-O notation for f(x) = 5logx is?
a) 1
b) x
c) x2
d) x3

Answer: b
Clarification: logx < x, it follows that 5logx < x.

10. The big-Omega notation for f(x) = 2x4 + x2 – 4 is?
a) x2
b) x3
c) x
d) x4

Answer: d
Clarification: 2x4 + x2 – 4 is greater than or equal to x4.

250+ TOP MCQs on Sequences and Summations and Answers

Discrete Mathematics Multiple Choice Questions on “Sequences and Summations”.

1. For the sequence 1, 7, 25, 79, 241, 727 … simple formula for {an} is ____________
a) 3n+1 – 2
b) 3n – 2
c) (-3)n + 4
d) n2 – 2

Answer: b
Clarification: The ratio of consecutive numbers is close to 3. Comparing these terms with the sequence of {3n} which is 3, 9, 27 …. Comparing these terms with the corresponding terms of sequence {3n} and the nth term is 2 less than the corresponding power of 3.

2. For the sequence 0, 1, 2, 3 an is ____________
a) ⌈n/2⌉+⌊n/2⌋
b) ⌈n/2⌉+⌈n/2⌉
c) ⌊n/2⌋+⌊n/2⌋
d) ⌊n/2⌋

Answer: a
Clarification: Expand the sequence ⌈n/2⌉+⌊n/2⌋ where a1 is ⌊0.5⌋+⌈0.5⌉ = 1+0 = 1, a2 is ⌊1⌋+⌈1⌉ = 1 + 1 = 2 and so on.

3. The value of∑(k=50)100 k2 is __________
a) 338, 350
b) 297, 900
c) 297, 925
d) 290, 025

Answer: c
Clarification: Using the formula. ∑(k=1)n k2 = (n(n + 1)(2n + 1)) / 6.

4. The sets A and B have same cardinality if and only if there is ___________ from A to B.
a) One-to-one
b) One-to-many
c) Many-to-many
d) Many-to-one

Answer: a
Clarification: If there is one-to-one correspondence then they have same cardinality.

5. For the sequence an = ⌊√2n+ 1/2⌋, a7is ____________
a) 1
b) 7
c) 5
d) 4

Answer: d
Clarification: a7 = ⌊√14+1/2⌋ which is ⌊4.24⌋ = 4.

6. The value of ∑(i=1)3 ∑(h=0)2 i is _________
a) 10
b) 17
c) 15
d) 18

Answer: d
Clarification: The value of ∑(i=1)3 ∑(h=0)2 i = 1+1+1+2+2+2+3+3+3 = 18.

7. For the sequence an = 6. (1/3)n, a4 is _________
a) 2/25
b) 2/27
c) 2/19
d) 2/13

Answer: b
Clarification: Put n = 4 in the sequence.

8. The value of ∑(i=0)4i! is __________
a) 32
b) 30
c) 34
d) 35

Answer: c
Clarification: First five term of the sequence n! is given by 1, 1, 2, 6, 24.

9. Set of all integers is counter.
a) True
b) False

Answer: a
Clarification: There is one-to-one correspondence between set of positive integers and set of all integers.

10. The value of ∏(k=1)100(-1) k is _________
a) 0
b) 1
c) -1
d) 2

Answer: b
Clarification: The product of a1, a2, a3 …… an is represented by ∏(i=1)n ai.

250+ TOP MCQs on Number Theory – Modular Exponentiation and Answers

Discrete Mathematics Multiple Choice Questions on “Number Theory – Modular Exponentiation”.

1. If the multiplicative inverse of “53 modulo 21” exists, then which of the following is true?
a) GCD(53,21) = 1
b) GCD(53,21) = 29
c) GCD(53,21) = 53
d) GCD(53,21) = 12

Answer: a
Clarification: The multiplicative inverse of “a modulo m” can be found out by extended Euler’s GCD algorithm, and the time complexity of this method is O(logm). We know that the multiplicative inverse of “x modulo n” exists if and only if x and n are relatively prime (i.e., if gcd(a, m) = 1). So, in this case GCD(53,21) = 1.

2. A multiplicative monoid defines the property of exponentiation with ________
a) integer exponents
b) fractional exponents
c) rational exponents
d) negative integer exponents

Answer: a
Clarification: Exponentiation with integer exponents is termed in any multiplicative monoid. Exponentiation is described inductively by 1) h0 = 1 for all h ∈ S, hn+1 = hn h and non-negative integers n, If n is a negative integer then hn is only defined if h has an inverse in S. Monoids define many structures including groups and rings (under multiplication).

3. Which of the following algorithms has better computational complexity than standard division algorithms?
a) Montgomery algorithm
b) Classical modular exponentiation algorithm
c) ASM algorithm
d) FSM algorithm

Answer: b
Clarification: To multiply m and n, they are converted to Montgomery form: mR mod X and nR mod X. When multiplied, these produce mnR2 mod X, and the Montgomery reduction produces abR mod N which is the Montgomery form of the desired product. After that, the low bits are discarded which gives a result less than 2X. One final subtraction reduces this to less than X. Hence, this procedure can have a better computational complexity than standard division algorithms.

4. Which of the following methods uses the concept that exponentiation is computationally inexpensive in the finite field?
a) Diffie-HEllman key exchange
b) RSA key exchange
c) Arithmetic key exchange
d) FSM method

Answer: a
Clarification: Exponentiation in the finite fields has its many applications in the public key cryptography system. Now, the Diffie–Hellman key exchange can have the concept that exponentiation is computationally inexpensive in the finite fields and the discrete logarithm which is the inverse of exponentiation, can be computationally expensive.

5. If there is a unique prime number p1 then a finite field F has the property of ______________
a) p1x = 0 for all x in F
b) f(x) = f(xp1) for all x in F
c) p1 = y for all y in F
d) xy + p1 for all x, y in F

Answer: a
Clarification: A field can be defined as an algebraic structure in which multiplication, addition, subtraction, and division are well-defined and satisfy similar properties. If there is a unique prime number p1 then a finite field F has the property of p1x = 0, for all x in F and this prime number is called the characteristics of the field.

6. Evaluate the expression 6359 mod 320.
a) 681
b) 811
c) 3781
d) 279

Answer: d
Clarification: By definition, we can have 6359 ≡ 279 (mod320), hence the answer is 279.

7. The time complexity to perform the modular exponentiation of a ≡ cg (mod m).
a) O(m+a)
b) O(a*g)
c) O(gm)
d) O(g)

Answer: d
Clarification: The modular exponentiation completely depends on the operating system environment and the processor for its performance. The above said method requires a time complexity of O(g) for its completion.

8. According to congruence relation, find the remainder of 56 mod 24.
a) 10
b) 12
c) 6
d) 4

Answer: c
Clarification: According to congruence relation, 56 ≡ 6 (mod 24), because 56 − 32 = 24, which is a multiple of 24. So, the remainder is 6.

9. In cryptography system, the value of z in x ≡ ze (mod m) should be at least ______
a) 1024 bits
b) 1GB
c) 596 bits
d) 54 Bytes

Answer: a
Clarification: In cryptography system, the value of z in x ≡ ze (mod m) should be at least 1024 bits.

10. Determine the value of x, where y = 7, e = 12 and n = 566 using modular exponentiation method (x ≡ ye (mod n)).
a) 735
b) 321
c) 872
d) 487

Answer: d
Clarification: Given y = 5, e = 12, and n = 566 and so x ≡ 512 (mod 566). Now 512 comes out to 244140625 and taking this value modulo 566, x is determined to be 487.

250+ TOP MCQs on Counting – Terms in Binomial Expansion

Discrete Mathematics Multiple Choice Questions on “Counting – Terms in Binomial Expansion”.

1. In a blindfolded game, a boy can hit the target 8 times out of 12. If he fired 8 shots, find out the probability of more than 4 hits?
a) 2.530
b) 0.1369
c) 0.5938
d) 3.998

Answer: c
Clarification: Here, n = 8, p = 0.6, q = 0.4. Suppose X = number of hits x0 = 0 number of hits, x1 = 1 hit, x2 = 2 hits, and so on.
So, (X) = P(x5) + P(x6) + P(x7) + P(x8) = 8C5(0.6)5(0.4)3 + 8C5(0.6)6(0.4)2 + 8C7(0.6)7(0.4)1 + 8C8(0.6)8(0.4)0 = 0.5938.

2. A fair coin is tossed 15 times. Determine the probability in which no heads turned up.
a) 2.549 * 10-3
b) 0.976
c) 3.051 * 10-5
d) 5.471

Answer: c
Clarification: According to the null hypothesis it is a fair coin and so in that case the probability of flipping at least 59% tails is = 15C0(0.5)15 = 3.051 * 10-5.

3. When a programmer compiles her code there is a 95% chance of finding a bug every time. It takes three hours to rewrite her code when she finds out a bug. Determine the probability such that she will finish her coding by the end of her workday. (Assume, a workday is 7 hours)
a) 0.065
b) 0.344
c) 0.2
d) 3.13

Answer: c
Clarification: A success is a bug-free compilation, and a failure is the finding out of a bug. The programmer has 0, 1, 2, or 3 failures and so her probability of finishing the program is : Pr(X=0) + Pr(X=1) + Pr(X=2) + Pr(X=3) = (0.95)0(0.05) + (0.95)0(0.05) + (0.95)0(0.05) + (0.95)0(0.05) = 0.2.

4. Determine the probability when a die is thrown 2 times such that there are no fours and no fives occur?
a) (frac{4}{9})
b) (frac{56}{89})
c) (frac{13}{46})
d) (frac{3}{97})

Answer: a
Clarification: In this experiment, throwing a die anything other than a 4 is a success and rolling a 4 is failure. Since there are two trials, the required probability is
b(2; 2, (frac{5}{6})) = 2C2 * ((frac{4}{6}))2 * ((frac{2}{6}))0 = (frac{4}{9}).

5. In earlier days, there was a chance to make a telephone call would be of 0.6. Determine the probability when it could make 11 successes in 20 attempts of phone call.
a) 0.2783
b) 0.2013
c) 0.1597
d) 3.8561

Answer: c
Clarification: Probability of success p=0.6 and q=0.4. X=success in making a telephone call. Hence, the probability of 11 successes in 20 attempts = P(X=11) = 20C11(0.6)11(0.4)20 – 11 = 0.1597.

6. By the expression (left(frac{x}{3} + frac{1}{x}right)^5), evaluate the middle term in the expression.
a) 10*(x5)
b) (frac{1}{5}*(frac{x}{4}))
c) 10*((frac{x}{3}))
d) 6*(x3)

Answer: c
Clarification: By using Binomial theorem,the expression (left(frac{x}{3} + frac{1}{x}right)^5) can be expanded as (left(frac{x}{3} + frac{1}{x}right)^5 = ^5C_0(frac{x}{3})^5 + ^5C_1(frac{x}{3})^4(frac{1}{x})^1 + ^5C_2(frac{x}{3})^3(frac{1}{x})^2)
(+ ^5C_3(frac{x}{3})^2(frac{1}{x})^3 + ^5C_4(frac{x}{3})^1(frac{1}{x})^4 )
= ((frac{x}{3})^5 + 5.(frac{x}{3}) + 10.(frac{x}{3}) + 10.(frac{1}{3x}) + 5(frac{1}{3x^3})). Hence, the middle term is 10*((frac{x}{3})).

7. Evaluate the expression (y+1)4 – (y-1)4.
a) 3y2 + 2y5
b) 7(y4 + y2 + y)
c) 8(y3 + y1)
d) y + y2 + y3

Answer: c
Clarification: By using Binomial theorem,the expression (y+1)4 – (y-1)4 can be expanded as = (y+1)4 = 4C0y4 + 4C1y3 + 4C2y2 + 4C3y1 + 4C4y0 and (y-1)4 = 4C0y44C1y3 + 4C2y24C3y1 + 4C4y0. Now, (y+1)4 – (y-1)4 = (4C0y4 + 4C1y3 + 4C2y2 + 4C3y1 + 4C4y0) – (4C0y44C1y3 + 4C2y24C3y1 + 4C4y0) = 2(4C1y3 + 4C3y1) = 8(y3 + y1).

8. Find the coefficient of x7 in (x+4)9.
a) 523001
b) 428700
c) 327640
d) 129024

Answer: d
Clarification: It is known that (r+1)th term, in the binomial expansion of (a+b)n is given by, Tr+1 = nCran-rbr. Assuming that x7 occurs in the (r+1)th term of the expansion (x+4)9, we obtain Tr+1 = 129024x4.

9. Determine the 7th term in the expansion of (x-2y)12.
a) 6128y7
b) 59136y6
c) 52632x6
d) 39861y5

Answer: b
Clarification: By assuming that x7 occurs in the (r+1)th term of the expansion (x-2y)12, we obtain Tr+1 = nCran-rbr = 12C6 x6 (2y)6 = 59136y6.

10. What is the middle term in the expansion of (x/2 + 6y)8?
a) 45360x4
b) 34210x3
c) 1207x4
d) 3250x5

Answer: a
Clarification: We know that in the expansion of (x+y)n, if n is even then the middle term is (n/2 + 1)th term. Hence, the middle term in the expansion of (x/2 + 6y)8 is (8/2+1)th = 5th term.
Now, assuming that x5 occurs in the (r+1)th term of the expansion (x/2+6y)8, we obtain Tr+1 =nCrxn-ryr = 8C4(x/2)4(6y)4 = 45360x4.