Category: Discrete Mathematics Objective Questions

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)= x^1/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) = 2^x 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) = x² + 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 x² is 0, thus x² +4 may take any value between [4,∞).

10. Let f(x)=sin²(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.

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) (n² + n + 2) / 2
b) (n³ + n – 2) / 2
c) (n² + n – 2) / 2
d) (n² – n – 2) / 2

Answer: c
Clarification: 2+3+4+….6n = (n² + 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(n²)
d) O(n log n)

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

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 2⁵⁶ cipher texts per plain text and a total of 2¹⁸ plaintexts of length 18 exists. Then determine the number of distinct ciphertexts?
a) 761
b) 2⁷⁴
c) 186
d) 2⁸⁹

Answer: b
Clarification: If there are 2⁵⁶ cipher texts per plain text and a total of 2¹⁸ plaintexts of length 18 exists which will all decrypt to the same plaintext, and this holds for every plaintext. There are a total of 2⁵⁶ plaintexts of length 56. Now, there must be 2⁵⁶. 2¹⁸ = 2⁷⁴ 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.

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

1. Calculate the value of ⁸C₅.
a) 79
b) 43
c) 120
d) 56

Answer: d
Clarification: We can use the formula ⁿC_k = (frac{n!}{k!(n-k)!}) to calculate the value of ⁸C₅ = (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 ¹⁷C₉ = (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 ⁶C₄ = 15. Hence, the total possible 4-digit numbers from the above 6 numbers are 15.

4. What is the coefficient of x⁹ in the expansion of (x+5)¹⁴?
a) 5! * ¹⁴C₆
b) ¹⁴C₅
c) 54 * ¹⁴C₅
d) 34 * ¹¹C₅

Answer: c
Clarification: the binomial theorem is (x+y)^a = Σ ^aC_i x^a-i yⁱ. In order to get the coefficient of x⁹, we need to have a-i=9. Since a=14, i=5. Thus, the answer is ^aC₅ * y⁴ = 5⁴ * ¹⁴C₅.

5. Determine the independent term of x⁷ in the expansion of (3x² + 4)¹².
a) 220 * 4⁶
b) 230
c) 548* 3!
d) 220 * 3⁶ * 4⁶

Answer: d
Clarification: By using Binomial theorem = ⁿ∑_k=0 (n^k) x^ky^n-k = n⁰x⁰yⁿ + n¹x¹y^n-1 + n²x²y^n-2 + … + nⁿxⁿy⁰, where (n^k) = (frac{n!}{k!(n−k)!}). Now, T_r+1 = ⁿC_ra^n-rb^r, T₉₊₁ = ¹²C₆a^12-6b⁶ = 220 * (3x²)⁶ * (4)⁶ = 220 * 3⁶ * 4⁶. Hence the coefficient is 220 * 3⁶ * 4⁶.

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 x⁸ in the expansion of (x+2)¹¹.
a) 640
b) 326
c) 1320
d) 456

Answer: c
Clarification: The coefficient of the 8^th term is ¹¹C₈ = 165. Hence, the 8^th term of the expansion is 165 * 2³ * x⁸ = 1320x⁸, where the coefficient is 1320.

8. Determine the coefficient of the x⁵y⁷ term in the polynomial expansion of (m+n)¹².
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 x⁵y⁷ must be equal to the number of combinations of 5 objects out of 12: ¹²C₅ = 792.

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

Answer: b
Clarification: Consider the binomial expansion of (m+1)⁷¹ and (m-1)⁷¹ which gives these two
expressions below respectively: 1) m⁵¹ + ⁵¹C₁m⁵⁰ + ⁵¹C₂m⁴⁹ + ⁵¹C₃m⁴⁸ + … + ⁵¹C₅₀m¹ + ⁵¹C₅₁m⁰
2) m⁵¹ – ⁵¹C₁m⁵⁰ + ⁵¹C₂m⁴⁹ – ⁵¹C₃m⁴⁸ + … + ⁵¹C₅₀m¹ – ⁵¹C₅₁m⁰ .
By taking the difference we have, 2(⁵¹C₁m⁵⁰ + ⁵¹C₃m⁴⁸ – ⁵¹C₅m⁴⁶ + … + ⁵¹C₅₀m² – ⁵¹C₅₁m⁰ ).
In this case, m = (sqrt{51}) and 2(⁵¹C₁m⁵⁰ + ⁵¹C₃m⁴⁸ – ⁵¹C₅m⁴⁶ + … + ⁵¹C₅₀m² – ⁵¹C₅₁m⁰ ).
Consider, module 10 on the powers(for any natural number n): (51)ⁿ ≡ (51 mod 10ⁿ) ≡ 1 gives 2(⁵¹C₁ + ⁵¹C₃ + ⁵¹C₅ + … + ⁵¹C₅₀ + ⁵¹C₅₁). Now, by adding the odd terms of the 51^st row of the Pascal Triangle 2.((frac{1}{2}) * 2⁵¹) = 2⁵¹ = 2^{(51 mod 4)} = 2³ = 8.

10. The independent term of x is 80000 in the expansion of (3x+b/x)⁶, 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 ⁶C_n * (4x)^6-n * (b/x)ⁿ.
For the term to be independent of x, we need x^6-n(1/x)ⁿ = x⁰ ⇒ x^6-n(x-1)ⁿ = x⁰ ⇒ x^6-nx^-n = x⁰ ⇒ 6 – n = n ⇒ 2n = 6 and n = 3. Thus, we have a constant term of ⁶C₃ * 3³ * b³ = 8000
20 * 27 * b³ = 80000
540 * b³ = 80000
b³ = 148.14 ⇒ b= 5.2.

Discrete Mathematics Multiple Choice Questions on “Relations – Equivalence Classes and Partitions”.

1. Suppose a relation R = {(3, 3), (5, 5), (5, 3), (5, 5), (6, 6)} on S = {3, 5, 6}. Here R is known as _________
a) equivalence relation
b) reflexive relation
c) symmetric relation
d) transitive relation

Answer: a
Clarification: Here, [3] = {3, 5}, [5] = {3, 5}, [5] = {5}. We can see that [3] = [5] and that S/R will be {[3], [6]} which is a partition of S. Thus, we can choose either {3, 6} or {5, 6} as a set of representatives of the equivalence classes.

2. Consider the congruence 45≡3(mod 7). Find the set of equivalence class representatives.
a) {…, 0, 7, 14, 28, …}
b) {…, -3, 0, 6, 21, …}
c) {…, 0, 4, 8, 16, …}
d) {…, 3, 8, 15, 21, …}

Answer: a
Clarification: Note that a set of class representatives is the subset of a set which contains exactly one element from each equivalence class. Now, for integers n, a and b, we have congruence a≡b(mod n), then the set of equivalence classes are {…, -2n, -n, 0, n, 2n,…}, {…, 1-2n, 1-n, 1, 1+n, 1+2n,…}. The required answer is {…, 0, 7, 14, 28, …}.

3. Which of the following relations is the reflexive relation over the set {1, 2, 3, 4}?
a) {(0,0), (1,1), (2,2), (2,3)}
b) {(1,1), (1,2), (2,2), (3,3), (4,3), (4,4)}
c) {,(1,1), (1,2), (2,1), (2,3), (3,4)}
d) {(0,1), (1,1), (2,3), (2,2), (3,4), (3,1)

Answer: b
Clarification: {(1,1), (1,2), (2,2), (3,3), (4,3), (4,4)} is a reflexive relation because it contains set = {(1,1), (2,2), (3,3), (4,4)}.

4. Determine the partitions of the set {3, 4, 5, 6, 7} from the following subsets.
a) {3,5}, {3,6,7}, {4,5,6}
b) {3}, {4,6}, {5}, {7}
c) {3,4,6}, {7}
d) {5,6}, {5,7}

Answer: b
Clarification: {3,5}, {3,6,7}, {4,5,6}. It is not a partition because these sets are not pairwise disjoint. The elements 3, 5 and 6 appear repeatedly these sets. {1}, {2,3,6}, {4}, {5} – this is a partition as they are pairwise disjoint. {3,4,6}, {7} – this is not a partition as element 5 is missing.
{5,6}, {5,7} – this is not a partition because it is missing the elements 3, 4 in any of the sets.

5. Determine the number of equivalence classes that can be described by the set {2, 4, 5}.
a) 125
b) 5
c) 16
d) 72

Answer: b
Clarification: Suppose B={2, 4, 5} and B×B = (2,2), (4,4), (5,5), (2,4), (4,2), (4,5), (5,4), (2,5), (5,2). A relation R on set B is said to be equivalence relation if R is reflexive, Symmetric, transitive. Hence, total number of equivalence relation=5 out of 2³=8 relations.

6. Determine the number of possible relations in an antisymmetric set with 19 elements.
a) 23585
b) 2.02 * 10⁸⁷
c) 9.34 * 7⁹¹
d) 35893

Answer: b
Clarification: Number of antisymmetric relation is given:-|A|=n, |AxA|=n xn. Then, N=total number of diagonal will n and we know that N = 2ⁿ * 3^(n2-n)/2. So, the number of relations should be = 2.02 * 10⁸⁷.

7. For a, b ∈ Z define a | b to mean that a divides b is a relation which does not satisfy ___________
a) irreflexive and symmetric relation
b) reflexive relation and symmetric relation
c) transitive relation
d) symmetric relation

Answer: b
Clarification: Suppose, a=0, then we know that 0 does not divide 0, 0 ∤ 0 and it is not reflexive. Again, 2 | 4 but 4 does not 2 and so it is not a symmetric relation.

8. Which of the following is an equivalence relation on R, for a, b ∈ Z?
a) (a-b) ∈ Z
b) (a²+c) ∈ Z
c) (ab+cd)/2 ∈ Z
d) (2c³)/3 ∈ Z

Answer: b
Clarification: Let a ∈ R, then a−a = 0 and 0 ∈ Z, so it is reflexive. To see that a-b ∈ Z is symmetric, then a−b ∈ Z -&gt say, a−b = m, where m ∈ Z ⇒ b−a = −(a−b)=−m and −m ∈ Z. Thus, a-b is symmetric. To see that a-b is transitive, let a, b, c ∈ R. Thus, a−b ∈ Z; b−c ∈ Z. Let a−b = i and b−c = j, for integers i,j ∈ Z. Then a−c ='(a−b)+(b−c)=i + j. So, a−c ∈ Z. Therefore a – c is transitive. Hence, (a-b) is an equivalence relation on the set R. Rest of the options are not equivalence relations.

9. Determine the set of all integers a such that a ≡ 3 (mod 7) such that −21 ≤ x ≤ 21.
a) {−21, −18, −11, −4, 3, 10, 16}
b) {−21, −18, −11, −4, 3, 10, 17, 24}
c) {−24, -19, -15, 5, 0, 6, 10}
d) {−23, −17, −11, 0, 2, 8, 16}

Answer: b
Clarification: For an integer a we have x ≡ 3 (mod 7) if and only if a = 7m + 3. Thus, by calculating multiples of 7, add 3 and restrict the value of a, so that −21 ≤ x ≤ 21. The set for a = {−21, −18, −11, −4, 3, 10, 17, 24}.

10. For a, b ∈ R define a = b to mean that |x| = |y|. If [x] is an equivalence relation in R. Find the equivalence relation for [17].
a) {,…,-11, -7, 0, 7, 11,…}
b) {2, 4, 9, 11, 15,…}
c) {-17, 17}
d) {5, 25, 125,…}

Answer: c
Clarification: We can find that [17] = {a ∈ R|a = 17} = {a ∈ R||a| = |17|} = {-17, 17} and [−17] = {a ∈ R|a = −17} = {a ∈ R||a| = |−17|}= {−17, 17}. Hence, the required equivalence relation is {-17, 17}.

Discrete Mathematics Multiple Choice Questions on “Boolean Algebra”.

1. Algebra of logic is termed as ______________
a) Numerical logic
b) Boolean algebra
c) Arithmetic logic
d) Boolean number

Answer: c
Clarification: The variables that can have two discrete values False(0) and True(1) and the operations of logical significance are dealt with Boolean algebra.

2. Boolean algebra can be used ____________
a) For designing of the digital computers
b) In building logic symbols
c) Circuit theory
d) Building algebraic functions

Answer: a
Clarification: For designing digital computers and building different electronic circuits boolean algebra is accepted widely.

3. What is the definition of Boolean functions?
a) An arithmetic function with k degrees such that f:Y–>Y^k
b) A special mathematical function with n degrees such that f:Yⁿ–>Y
c) An algebraic function with n degrees such that f:Xⁿ–>X
d) A polynomial function with k degrees such that f:X²–>Xⁿ

Answer: b
Clarification: A Boolean function is a special mathematical function with n degrees and where Y = {0,1} is the Boolean domain with being a non-negative integer. It helps in describing the way in which the Boolean output is derived from Boolean inputs.

4. F(X,Y,Z,M) = X`Y`Z`M`. The degree of the function is ________
a) 2
b) 5
c) 4
d) 1

Answer: c
Clarification: This is a function of degree 4 from the set of ordered pairs of Boolean variables to the set {0,1}.

5. A ________ value is represented by a Boolean expression.
a) Positive
b) Recursive
c) Negative
d) Boolean

Answer: d
Clarification: A Boolean value is given by a Boolean expression which is formed by combining Boolean variables and logical connectives.

6. Which of the following is a Simplification law?
a) M.(~M+N) = M.N
b) M+(N.O) = (M+N)(M+O)
c) ~(M+N) = ~M.~N
d) M.(N.O) = (M.N).O

Answer: a
Clarification: By Simplification Law we can have X.(~X+Y) = X.Y and X+(~X.Y) = X+Y. By, De’ Morgan’s law ~(X+Y) = ~X.~Y. By commutative law we can say that A.(B.C) = (A.B).C.

7. What are the canonical forms of Boolean Expressions?
a) OR and XOR
b) NOR and XNOR
c) MAX and MIN
d) SOM and POM

Answer: d
Clarification: There are two kinds of canonical forms for a Boolean expression-> 1)sum of minterms(SOM) form and
2)product of maxterms(SOM) form.

8. Which of the following is/are the universal logic gates?
a) OR and NOR
b) AND
c) NAND and NOR
d) NOT

Answer: c
Clarification: NAND and NOR gates are known as the universal logic gates. A universal gate is a gate which can implement any Boolean function without the help of 3 basic gate types.

9. The logic gate that provides high output for same inputs ____________
a) NOT
b) X-NOR
c) AND
d) XOR

Answer: b
Clarification: The logic gate which gives high output for the same inputs, otherwise low output is known as X-NOR or Exclusive NOR gate.

10. The ___________ of all the variables in direct or complemented from is a maxterm.
a) addition
b) product
c) moduler
d) subtraction

Answer: a
Clarification: The Boolean function is expressed as a sum of the 1-minterms and the inverse of function is represented as 0-minterms.