250+ TOP MCQs on Groups – Burnside Theorem and Answers

Discrete Mathematics Multiple Choice Questions on “Groups – Burnside Theorem”.

1. Which of the following is not an abelian group?
a) semigroup
b) dihedral group
c) trihedral group
d) polynomial group

Answer: b
Clarification: The dihedral group(Dih4) of order 8 is a non-abelian p-group. But, every group of order p2 must be abelian group.

2. If we take a collection of {∅, {2}, {3}, {5}} ordered by inclusion. Which of the following is true?
a) isomorphic graph
b) poset
c) lattice
d) partially ordered set

Answer: b
Clarification: This is a poset. Since {2}, {3} and {5} have no common upper bound, it is not a lattice.

3. _______ characterizes the properties of distributive lattices.
a) Congruence Extension Property
b) Algebraic extension property
c) Poset
d) Semigroup

Answer: b
Clarification: An algebra A describes the congruence extension property (CEP) if for every B≤A and θ∈Con(B) there exists a φ∈Con(A) such that θ = φ∩(B×B). A class M of algebras has the CEP if every algebra in the class has the CEP. The Congruence Extension Property specifically characterizes the distributive lattices among all lattices.

4. Suppose that H be an X-set and suppose that a∼b and |Xa|=|Xb|, the which of the following is true?
a) Xa is powerset of Xb
b) Xa is isomorphic to Xb
c) Xa is homomorphic to Xb
d) Xb is the subset of Xa

Answer: b
Clarification: According to Burnside theorem, Xa is isomorphic to Xb and in particular |Xa|=|Xb|.

5. If he 4 sides of a square are to be colored by colors. How many different colourings with 50 colours are there if two arrangements that can be obtained from each other by rotation are identical?
a) 773762
b) 363563
c) 4536822
d) 1563150

Answer: d
Clarification: There are m4 + m2 + 2m elements after performing all rotations. Dividing this by the number of transformations 4 produces the desired number of distinct colorings (frac{m^4 + m^2 + 2m}{4}). Hence, the number of distinct colorings with 50 colors is 1563150.

6. Let H be a finite group. The order of Sylow p-subgroup of H for every prime factor p with multiplicity 9 is?
a) p+6
b) p9
c) pp
d) 3!*p2

Answer: b
Clarification: We know that, for a finite group H, there exists a Sylow p-subgroup of H having order p9 for every prime factor p with multiplicity 9.

7. How many indistinguishable necklaces can be made from beads of 4 colors with exactly 9 beads of each color where each necklace is of length 16?
a) 76967234
b) 5652209
c) 14414400
d) 8686214

Answer: c
Clarification: If B is the set of all possible permutations of these 16 beads, then the required answer is |B| = 16!/(9!)4 = 14414400.

8. Invariant permutations of two functions can form __________
a) groups
b) lattices
c) graphs
d) rings

Answer: a
Clarification: Suppose, there are two functions f1 and f2 which belong to the same equivalence class since there exists an invariant permutation say, π(a permutation that does not change the object itself, but only its representation), such that: f2*π≡f1. So, invariant permutations can form a group, as the product (composition) of invariant permutations is again an invariant permutation.

9. Suppose P(h) is a group of permutations and identity permutation(id) belongs to P(c). If ϕ(c)=c then which of the following is true?
a) ϕ-1∈P(h)
b) ϕ-1∈P(h)
c) ϕ-1∈P(h)
d) ϕ-1∈P(h)

Answer: b
Clarification: Let, ϕ and σ both can fix h, then we can have ϕ(σ(h)) = ϕ(h) = h. Hence, ϕ∘σ fixes h and ϕ∘σ∈P(h). Now, all colorings can be fixed by the identity permutation. So id∈P(h) and if ϕ(h) = h then ϕ-1(h) = ϕ-1(ϕ(h)) = id(h) = h which implies that ϕ-1∈P(h).

10. An isomorphism of Boolean algebra is defined as _______
a) order isomorphism
b) unordered isomorphism
c) order homomorphism
d) hyper-morphism

Answer: a
Clarification: We know that very σ-complete Boolean algebra is a Boolean algebra. An isomorphism of Boolean algebras is termed as an order isomorphism. All meets and joins present in an order isomorphism domain is preserved. Hence, a Boolean algebra isomorphism preserves all meets and joins in its domain.

250+ TOP MCQs on Logics – Tautologies and Contradictions

Discrete Mathematics Questions and Answers for Experienced people on “Logics – Tautologies and Contradictions”.

1. A compound proposition that is always ___________ is called a tautology.
a) True
b) False

Answer: a
Clarification: Tautology is always true.

2. A compound proposition that is always ___________ is called a contradiction.
a) True
b) False

Answer: b
Clarification: Contradiction is always false.

3. If A is any statement, then which of the following is a tautology?
a) A ∧ F
b) A ∨ F
c) A ∨ ¬A
d) A ∧ T

Answer: c
Clarification: A ∨ ¬A is always true.

4. If A is any statement, then which of the following is not a contradiction?
a) A ∧ ¬A
b) A ∨ F
c) A ∧ F
d) None of mentioned

Answer: b
Clarification: A ∨ F is not always false.

5. A compound proposition that is neither a tautology nor a contradiction is called a ___________
a) Contingency
b) Equivalence
c) Condition
d) Inference

Answer: a
Clarification: Definition of contingency.

6. ¬ (A ∨ q) ∧ (A ∧ q) is a ___________
a) Tautology
b) Contradiction
c) Contingency
d) None of the mentioned

Answer: b
Clarification: ≡ (¬A ∧ ¬q) ∧ (A ∧ q)
≡ (¬A ∧ A) ∧ (¬q ∧ q)
≡ F ∧ F ≡ F.

7. (A ∨ ¬A) ∨ (q ∨ T) is a __________
a) Tautology
b) Contradiction
c) Contingency
d) None of the mentioned

Answer: a
Clarification: ≡ (A ∨ ¬A) ∨ (q ∨ T)
≡ T ∨ T ≡ T.

8. A ∧ ¬(A ∨ (A ∧ T)) is always __________
a) True
b) False

Answer: b
Clarification: ≡ A ∧ ¬ (A ∨ (A ∧ T))
≡ A ∧ ¬(A ∨ A)
≡ A ∧ ¬A ≡ F.

9. (A ∨ F) ∨ (A ∨ T) is always _________
a) True
b) False

Answer: a
Clarification: ≡ (A ∨ F) ∨ (A ∨ T)
≡ A ∨ T ≡ T.

10. A → (A ∨ q) is a __________
a) Tautology
b) Contradiction
c) Contingency
d) None of the mentioned

Answer: a
Clarification: ≡ A → (A ∨ q)
≡ ¬A ∨ (A ∨ q)
≡ (A ∨ ¬A) ∨ q
≡ T ∨ q ≡ T.

250+ TOP MCQs on Domain and Range of Functions and Answers

Discrete Mathematics MCQs on “Domain and Range of Functions”.

1. What is the domain of a function?
a) the maximal set of numbers for which a function is defined
b) the maximal set of numbers which a function can take values
c) it is a set of natural numbers for which a function is defined
d) none of the mentioned

Answer: a
Clarification: Domain is the set of all the numbers on which a function is defined. It may be real as well.

2. What is domain of function f(x)= x1/2?
a) (2, ∞)
b) (-∞, 1)
c) [0, ∞)
d) None of the mentioned

Answer: c
Clarification: A square root function is not defined for negative real numbers.

3. What is the range of a function?
a) the maximal set of numbers for which a function is defined
b) the maximal set of numbers which a function can take values
c) it is set of natural numbers for which a function is defined
d) none of the mentioned

Answer: b
Clarification: Range is the set of all values which a function may take.

4. What is domain of function f(x) = x-1 for it to be defined everywhere on domain?
a) (2, ∞)
b) (-∞, ∞) – {0}
c) [0, ∞)
d) None of the mentioned

Answer: b
Clarification: Function x-1 is not defined for x=0, otherwise it defined for every real number.

5. The range of function f(x) = sin(x) is (-∞, ∞).
a) True
b) False

Answer: b
Clarification: A sine function takes values between -1 and 1,thus range is [-1, 1].

6. Codomain is the subset of range.
a) True
b) False

Answer: b
Clarification: Range is the subset of codomain, that is every value in the range is in codomain but vice-versa it is not true.

7. What is range of function f(x) = x-1 which is defined everywhere on its domain?
a) (-∞, ∞)
b) (-∞, ∞) – {0}
c) [0, ∞)
d) None of the mentioned

Answer: a
Clarification: Function x-1 may take any real number hence it’s range is all real numbers.

8. If f(x) = 2x then range of the function is?
a) (-∞, ∞)
b) (-∞, ∞) – {0}
c) (0, ∞)
d) None of the mentioned

Answer: c
Clarification: The function cannot take negative values,hence range is (0, ∞).

9. If f(x) = x2 + 4 then range of f(x) is given by?
a) [4, ∞)
b) (-∞, ∞) – {0}
c) (0, ∞)
d) None of the mentioned

Answer: a
Clarification: Since minimum value of x2 is 0, thus x2 +4 may take any value between [4,∞).

10. Let f(x)=sin2(x) + log(x) then domain of f(x) is (-∞, ∞).
a) True
b) False

Answer: b
Clarification: Domain is (0, ∞), since log(x) is not defined for negative numbers and zero.

250+ TOP MCQs on Algorithms and Answers

Discrete Mathematics Multiple Choice s on “Algorithms”.

1. An algorithm is a _________ set of precise instructions for performing computation.
a) Infinite
b) Finite
c) Constant
d) None of the mentioned

Answer: b
Clarification: By the definition of an algorithm.

2. Out of the following which property algorithms does not share?
a) Input
b) Finiteness
c) Generality
d) Constancy

Answer: d
Clarification: All the others are the properties of algorithms.

3. In ________ search each element is compared with x till not found.
a) Binary
b) Sequential
c) Merge
d) None of the mentioned

Answer: b
Clarification: In linear or sequential search entire list is searched sequentially for x.

4. If the entire list is searched sequentially without locating x in linear search, the solution is __________
a) 0
b) -1
c) 1
d) 2

Answer: a
Clarification: If the element is not found in the entire list, then the solution is 0.

5. To sort a list with n elements, the insertion sort begins with the __________ element.
a) First
b) Second
c) Third
d) Fourth

Answer: b
Clarification: The insertion sort compares the second element with the first element to start sorting.

6. __________ comparisons required to sort the list 1, 2, 3…….n using insertion sort.
a) (n2 + n + 2) / 2
b) (n3 + n – 2) / 2
c) (n2 + n – 2) / 2
d) (n2 – n – 2) / 2

Answer: c
Clarification: 2+3+4+….6n = (n2 + n – 2) / 2.

7. The Worst case occurs in linear search algorithm when ____________
a) Item is somewhere in the middle of the array
b) Item is not in the array at all
c) Item is the last element in the array
d) Item is the last element in the array or is not there at all

Answer: d
Clarification: The Worst case occur in linear search algorithm when Item is the last element in the array or is not there at all.

8. List obtained in third pass of selection sort for list 3, 5, 4, 1, 2 is ___________
a) 1, 2, 4, 3, 5
b) 1, 2, 3, 4, 5
c) 1, 5, 4, 3, 2
d) 3, 5, 4, 1, 2

Answer: b
Clarification: The selection sort begins with finding the least element in the list. This element is moved to front and then the least element among the remaining elements. Is found and put into the second position and so on.

9. The operation of processing each element in the list is known as _________
a) Sorting
b) Merging
c) Inserting
d) Traversal

Answer: d
Clarification: The operation of processing each element in the list is known as Traversal.

10. The complexity of Bubble sort algorithm is _________
a) O(n)
b) O(log n)
c) O(n2)
d) O(n log n)

Answer: c
Clarification: The complexity of Bubble sort algorithm is O(n2).

250+ TOP MCQs on Cryptography – Encryption and Answers

Discrete Mathematics Multiple Choice Questions on “Cryptography – Encryption”.

1. How many bytes of the secret key is generated using Diffie-Hellman encryption/decryption scheme?
a) 256
b) 871
c) 1024
d) 962

Answer: a
Clarification: Diffie-Hellman encryption/decryption scheme generates 256 bytes shared a secret key. This secret key then is used by AES key to encrypt this data.

2. In which of the following systems, encryption slower than decryption?
a) elliptic curve cryptography
b) parabolic curve cryptography
c) symmetric cryptography
d) antisymmetric cryptography

Answer: b
Clarification: It is known that performing encryption using the public key takes more time than performing decryption using the private key in elliptic curve cryptography (ECC) and the key consists of 60 bytes.

3. If there are 256 cipher texts per plain text and a total of 218 plaintexts of length 18 exists. Then determine the number of distinct ciphertexts?
a) 761
b) 274
c) 186
d) 289

Answer: b
Clarification: If there are 256 cipher texts per plain text and a total of 218 plaintexts of length 18 exists which will all decrypt to the same plaintext, and this holds for every plaintext. There are a total of 256 plaintexts of length 56. Now, there must be 256. 218 = 274 distinct ciphertexts which all decrypt to plaintexts of length 56. If all those ciphertexts are the same length, they must be at least 74 bits long.

4. TEA cipher uses which of the following structure?
a) standard cipher structure
b) pseudo random structure
c) feistel structure
d) block structure

Answer: c
Clarification: The Feistel structure system TEA operates on two 32-bit unsigned integer numbers. It uses a 128-bit key that can be used to build a simple key schedule by mixing all of the key elements.

5. Let A’s public key is n=6, 736, 180, 7817, 961, 456, 267 and e = 5 and B sends the ciphertext. c = 456, 871, 122, 391, 882, 538 to A. Determine B’s message in numeric format?
a) 235813
b) 57971.89
c) 770190.04
d) 687651.9

Answer: c
Clarification: It is known that to get original message m after decrypting we can have the formula m=c1/e. In this case: (456,871,122,391,882,538)1/3 = 770190.04 and this is the required answer.

6. In encryption, which of the following is the best text encoding technique?
a) ASCII encoding
b) Hex-encoding
c) Unicode technique
d) Base64 encoding

Answer: c
Clarification: Base64 and hex encoding scheme encode characters(or only bytes). First, we need to encode the characters as bytes and after that encode the bytes. In terms of compactness and simplicity, the best technique is Unicode scheme.

7. _______ are used as the base of the Public Key Infrastructure.
a) SSL certificates
b) TLS certificates
c) X.509 certificates
d) HAS certificates

Answer: c
Clarification: The X.509 certificates may be used as a base of the Public Key Infrastructure. PKIX is a tree structure where a Certificate Authority can be used to give trust to end entity certificates. X.509 certificates cannot directly use symmetric cryptography.

8. The default key size of RC2 Feistel cipher is _______
a) 64GB
b) 64 bits
c) 64 bytes
d) 64KB

Answer: c
Clarification: RC2 is a 64-bit source-heavy Feistel cipher system with a default key size of 64 bits. It is a complex cipher which uses secret indices and performs bitwise rotations, logical operations(AND, NOT, and OR) and modular addition.

9. How many combinations of keys can be constructed from a 72 ciphertext stream cipher?
a) 4271
b) 7345
c) 3291
d) 2556

Answer: d
Clarification: For stream cipher, if there are n ciphertexts then there are n*(n−1)/2 combination of keys to be made.
= (72*frac{72-1}{2})
= 72*35.5
= 2556.

10. What is the block size of RC6 Feistel block cipher?
a) 5013 bits
b) 128 bits
c) 596 bits
d) 1768 bits

Answer: b
Clarification: The RC6 Feistel block cipher is a 20-round cipher scheme which includes a fixed block size of 128 bits and it supports 128, 192, and 256-bit keys for encryption of messages.

250+ TOP MCQs on Counting – Binomial Coefficient and Answers

Discrete Mathematics Multiple Choice Questions on “Counting – Binomial Coefficient”.

1. Calculate the value of 8C5.
a) 79
b) 43
c) 120
d) 56

Answer: d
Clarification: We can use the formula nCk = (frac{n!}{k!(n-k)!}) to calculate the value of 8C5 = (frac{8!}{5!(8-5)!}) = 56.

2. In how many ways can you select 9 cupcakes from a box containing 17 cupcakes?
a) 42769
b) 45398
c) 24310
d) 36214

Answer: c
Clarification: The number of ways to choose 9 cupcakes out of a set of 17 is 17C9 = (frac{17!}{9!(17-9)!}) = 24,310.

3. How many 4-digit numbers can be formed by using 2, 4, 6, 8, 10, 12 without repetition of digits?
a) 15
b) 42
c) 70
d) 127

Answer: a
Clarification: Here making a 4-digit number is equivalent to filling 4 places with 6 numbers. So, the number of ways of filling all the four places is 6C4 = 15. Hence, the total possible 4-digit numbers from the above 6 numbers are 15.

4. What is the coefficient of x9 in the expansion of (x+5)14?
a) 5! * 14C6
b) 14C5
c) 54 * 14C5
d) 34 * 11C5

Answer: c
Clarification: the binomial theorem is (x+y)a = Σ aCi xa-i yi. In order to get the coefficient of x9, we need to have a-i=9. Since a=14, i=5. Thus, the answer is aC5 * y4 = 54 * 14C5.

5. Determine the independent term of x7 in the expansion of (3x2 + 4)12.
a) 220 * 46
b) 230
c) 548* 3!
d) 220 * 36 * 46

Answer: d
Clarification: By using Binomial theorem = nk=0 (nk) xkyn-k = n0x0yn + n1x1yn-1 + n2x2yn-2 + … + nnxny0, where (nk) = (frac{n!}{k!(n−k)!}). Now, Tr+1 = nCran-rbr, T9+1 = 12C6a12-6b6 = 220 * (3x2)6 * (4)6 = 220 * 36 * 46. Hence the coefficient is 220 * 36 * 46.

6. In a game, a fair coin is tossed 6 times. Each time the coin comes up tails, A will pay Rs. 15 but if each time heads come up, A will pay nothing. Determine the probability that A will win Rs. 45 by playing the game?
a) (frac{5}{16})
b) (frac{4}{31})
c) (frac{3}{7})
d) (frac{12}{65})

Answer: a
Clarification: By using the binomial distribution, to calculate how likely to win Rs. 45 (or equivalently, the likelihood the coin comes up tails 3 times). The possible outcomes of this game are to win Rs. 45. Therefore, the required probability is (frac{^6C_3}{26} = frac{5}{16}).

7. Find the coefficient of x8 in the expansion of (x+2)11.
a) 640
b) 326
c) 1320
d) 456

Answer: c
Clarification: The coefficient of the 8th term is 11C8 = 165. Hence, the 8th term of the expansion is 165 * 23 * x8 = 1320x8, where the coefficient is 1320.

8. Determine the coefficient of the x5y7 term in the polynomial expansion of (m+n)12.
a) 792
b) 439
c) 382
d) 630

Answer: a
Clarification: Note that, the “x” in the binomial has to be chosen 5 times out of 12. Thus, the coefficient of the term x5y7 must be equal to the number of combinations of 5 objects out of 12: 12C5 = 792.

9. The last digit of the number (((sqrt{51}) + 1)51 – (sqrt{51}) – 1)51 is _______
a) 32
b) 8
c) 51
d) 1

Answer: b
Clarification: Consider the binomial expansion of (m+1)71 and (m-1)71 which gives these two
expressions below respectively: 1) m51 + 51C1m50 + 51C2m49 + 51C3m48 + … + 51C50m1 + 51C51m0
2) m5151C1m50 + 51C2m4951C3m48 + … + 51C50m151C51m0 .
By taking the difference we have, 2(51C1m50 + 51C3m4851C5m46 + … + 51C50m251C51m0 ).
In this case, m = (sqrt{51}) and 2(51C1m50 + 51C3m4851C5m46 + … + 51C50m251C51m0 ).
Consider, module 10 on the powers(for any natural number n): (51)n ≡ (51 mod 10n) ≡ 1 gives 2(51C1 + 51C3 + 51C5 + … + 51C50 + 51C51). Now, by adding the odd terms of the 51st row of the Pascal Triangle 2.((frac{1}{2}) * 251) = 251 = 2(51 mod 4) = 23 = 8.

10. The independent term of x is 80000 in the expansion of (3x+b/x)6, where b is a positive constant. What the value of b?
a) 3.97
b) 6.87
c) 8.3
d) 5.2

Answer: d
Clarification: By using the Binomial Theorem, the terms are of the form 6Cn * (4x)6-n * (b/x)n.
For the term to be independent of x, we need x6-n(1/x)n = x0 ⇒ x6-n(x-1)n = x0 ⇒ x6-nx-n = x0 ⇒ 6 – n = n ⇒ 2n = 6 and n = 3. Thus, we have a constant term of 6C3 * 33 * b3 = 8000
20 * 27 * b3 = 80000
540 * b3 = 80000
b3 = 148.14 ⇒ b= 5.2.