Category: Discrete Mathematics Objective Questions

Discrete Mathematics Multiple Choice Questions on “Algorithms – Types”.

1. An Algorithm is ___________
a) A procedure for solving a problem
b) A problem
c) A real life mathematical problem
d) None of the mentioned

Answer: a
Clarification: An algorithm is a stepwise solution to the problem.

2. An algorithm in which we divide the problem into subproblem and then we combine the subsolutions to form solution to the original problem is known as _________
a) Brute Force
b) Divide and Conquer
c) GreedyAlgorithm
d) None of the mentioned

Answer: b
Clarification: In Divide and Conquer we divide the problem and then recombine the solution.

3. An algorithm which uses the past results and uses them to find the new results is _________
a) Brute Force
b) Divide and Conquer
c) Dynamic programming algorithms
d) None of the mentioned

Answer: c
Clarification: In Dynamic programming algorithms we utilize previous results for new ones.

4. A Complexity of algorithm depends upon _________
a) Time only
b) Space only
c) Both Time and Space
d) None of the mentioned

Answer: c
Clarification: For Complexity, we calculate both time and space consumed.

5. An algorithm which tries all the possibilities unless results are satisfactory is and generally is time-consuming is _________
a) Brute Force
b) Divide and Conquer
c) Dynamic programming algorithms
d) None of the mentioned

Answer: a
Clarification: In Brute force, all the possibilities are tried.

6. For a recursive algorithm _________
a) a base case is necessary and is solved without recursion.
b) a base case is not necessary
c) doesnot solve a base case directly
d) none of the mentioned

Answer: b
Clarification: Base case ends recursion and therefore it is necessary for finite recursion.

7. Optimization of algorithm means _________
a) making that algorithm fast by time and compact by space
b) making that algorithm slow by time and large by space
c) making that algorithm fast by time and large by space
d) making that algorithm slow by time and compact by space

Answer: a
Clarification: An Algorithm should be fast and compact.

8. For an algorithm which is the most important characteristic that makes it acceptable _________
a) Fast
b) Compact
c) Correctness and Precision
d) None of the mentioned

Answer: c
Clarification: An algorithm should be correct otherwise it’s of no use even if it is fast and compact.

9. An algorithm: can be represented through _________
a) flow charts
b) pseudo codes
c) instructions in common language
d) all of the mentioned

Answer: d
Clarification: Algorithm is represented through pseudo codes, normal language sentences or flow charts.

10. There are two algorithms suppose A takes 1.41 milli seconds while B takes 0.9 milliseconds, which one of them is better considering all other things the same?
a) A is better than B
b) B is better than A
c) Both are equally good
d) None of the mentioned

Answer: b
Clarification: B takes less time than A for the same task.

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

1. Suppose that there are two primes, P₁ = 229 and p₂ = 61. Find the value of z and Φ.
a) 13969, 13680
b) 5853, 23452
c) 7793, 34565
d) 17146, 69262

Answer: a
Clarification: We know that, z = p₁*p₂ = 229*61 = 13969 and Φ = (p₁ – 1)(p₂ – 1) = (229 – 1)(61 – 1) = 228*60 = 13680.

2. ________ can decrypt traffic to make it available to all other network security functions such as web proxies.
a) SSL visibility appliances
b) RSA appliances
c) Rodriguez cipher system
d) Standard cipher system

Answer: a
Clarification: In the data loss prevention systems, Web proxies and antivirus network security functions, SSL visibility appliances decrypt traffic to make it available for all networks.

3. The ROT13 caesar cipher system has an offset of ___________
a) 13
b) 45
c) 71
d) 37

Answer: a
Clarification: The ROT13 Caesar cipher system has an offset of 13 and it is one of the comprehensive cipher scheme. However, the Vigenere cipher employs Caesar cipher as one element of the encryption process.

4. In a public key system, the cipher text received is C = 10 if RSA encryption used with a public key(e = 11, n = 77) to deduce the plain text. Determine the value of ϕ(n)?
a) 49
b) 60
c) 123
d) 70

Answer: b
Clarification: Given n = 77, that means p and q must be 7 and 11 that is they must be co-prime to each other. Now we know that ϕ(n) = (p – 1) (q – 1)
ϕ(n) = (7 – 1) (11 – 1)
ϕ(n) = 6*10
ϕ(n) = 60.

5. To encrypt a message _______ is used on the character’s positions.
a) boolean algebra
b) bijective function
c) inverse function
d) surjective function

Answer: b
Clarification: We have a mathematical notion that a bijective function can be used on the characters’ positions to encrypt a message and an inverse function is used to decrypt the message.

6. The public key of given user, in an RSA encryption system is e = 57 and n = 3901. What is the value of Euler’s totient function ϕ(n) for calculating the private key of the user?
a) 4369
b) 3772
c) 871
d) 7892

Answer: b
Clarification: Given that n=3901 and e=31. We know that n = p∗q where p and q are prime numbers, which gives 3901 = 47*83. Now, ϕ(n) is Euler’s totient function i.e., ϕ(n) = (p−1)∗(q−1)
ϕ(n) = (47−1)∗(83−1)
ϕ(n) = 46*82 = 3772.

7. Using RSA algorithm what is the value of cipher test c if the plain text e = 7 and P = 5, q = 16 & n = 832. Determine the Euler’s totient function for the plain text?
a) 47
b) 584
c) 428
d) 60

Answer: d
Clarification: Given plain text (m) = 7, P = 5, Q = 16, where P and Q are two prime integer
n = P * Q ⇒ n = 5*16 = 80 ⇒ Z = (P-1)*(Q-1) ⇒ Z = (5-1)*(16-1) = 4*15 = 60.

8. There are 67 people in a company where they are using secret key encryption and decryption system for privacy purpose. Determine the number of secret keys required for this purpose?
a) 887
b) 6529
c) 2211
d) 834

Answer: c
Clarification: Since every two employee have their own secret key encryption and decryption. Both users have to agree on a secret key to communicate using symmetric cryptography. After that, each message is encrypted with that key it is transmitted and decrypted with the same key. Here, key distribution must be secret. For n = 67 we would need (frac{n(n-1)}{2} = frac{67(67-1)}{2}) = 2211 keys.

9. In a transposition cipher, the plaintext is constructed by the ________ of the ciphertext.
a) permutation
b) combination
c) sequence
d) series

Answer: a
Clarification: In cryptography, a method of encryption where the positions of plaintext held by units are shifted according to a regular system so that the ciphertext constructs a permutation of the plaintext is termed as transposition cipher.

10. How many bits of message does the Secure Hash Algorithm produce?
a) 160 bits
b) 1035 bits
c) 621 bits
d) 3761 bits

Answer: a
Clarification: The Secure Hash Algorithm or SHA is based on MD4 encryption system. This algorithm gives an output of a longer 160-bit message that is why it is harder to construct another message that yields the same resultant message.

Discrete Mathematics Multiple Choice Questions on “Advanced Counting Techniques – Recurrence Relation”.

1. Consider the recurrence relation a₁=4, a_n=5n+a_n-1. The value of a₆₄ is _________
a) 10399
b) 23760
c) 75100
d) 53700

Answer: a
Clarification: a_n=5n+a_n-1
= 5n + 5(n-1) + … + a_n-2
= 5n + 5(n-1) + 5(n − 2) +…+ a₁
= 5n + 5(n-1) + 5(n − 2) +…+ 4 [since, a1=4]
= 5n + 5(n-1) + 5(n − 2) +…+ 5.1 – 1
= 5(n + (n − 1)+…+2 + 1) – 1
= 5 * n(n+1)/ 2 – 1
a_n = 5 * n(n+1)/ 2 – 1
Now, n=64 so the answer is a₆₄ = 10399.

2. Determine the solution of the recurrence relation F_n=20F_n-1 − 25F_n-2 where F₀=4 and F₁=14.
a) a_n = 14*5^n-1
b) a_n = 7/2*2ⁿ−1/2*6ⁿ
c) a_n = 7/2*2ⁿ−3/4*6ⁿ⁺¹
d) a_n = 3*2ⁿ−1/2*3ⁿ

Answer: b
Clarification: The characteristic equation of the recurrence relation is → x²−20x+36=0
So, (x-2)(x-18)=0. Hence, there are two real roots x₁=2 and x₂=18. Therefore the solution to the recurrence relation will have the form: a_n=a2ⁿ+b18ⁿ. To find a and b, set n=0 and n=1 to get a system of two equations with two unknowns: 4=a2⁰+b18⁰=a+b and 3=a2¹+b6¹=2a+6b. Solving this system gives b=-1/2 and a=7/2. So the solution to the recurrence relation is,
a_n = 7/2*2ⁿ−1/2*6ⁿ.

3. What is the recurrence relation for 1, 7, 31, 127, 499?
a) b_n+1=5b_n-1+3
b) b_n=4b_n+7!
c) b_n=4b_n-1+3
d) b_n=b_n-1+1

Answer: c
Clarification: Look at the differences between terms: 1, 7, 31, 124,…. and these are growing by a factor of 4. So, 1⋅4=4, 7⋅4=28, 31⋅4=124, and so on. Note that we always end up with 3 less than the next term. So, b_n=4b_n-1+3 is the recurrence relation and the initial condition is b₀=1.

4. If S_n=4S_n-1+12n, where S₀=6 and S₁=7, find the solution for the recurrence relation.
a) a_n=7(2ⁿ)−29/6n6ⁿ
b) a_n=6(6ⁿ)+6/7n6ⁿ
c) a_n=6(3ⁿ⁺¹)−5n
d) a_n=nn−2/6n6ⁿ

Answer: b
Clarification: The characteristic equation of the recurrence relation is → x²−4x-12=0
So, (x-6)(x+2)=0. Only the characteristic root is 6. Therefore the solution to the recurrence relation will have the form: a_n=a.6ⁿ+b.n.6ⁿ. To find a and b, set n=0 and n=1 to get a system of two equations with two unknowns: 6=a6⁰+b.0.6⁰=a and 7=a6¹+b.1.6¹=2a+6b. Solving this system gives a=6 and b=6/7. So the solution to the recurrence relation is, a_n=6(6ⁿ)−6/7n6ⁿ.

5. Find the value of a₄ for the recurrence relation a_n=2a_n-1+3, with a₀=6.
a) 320
b) 221
c) 141
d) 65

Answer: c
Clarification: When n=1, a₁=2a₀+3, Now a₂=2a₁+3. By substitution, we get a₂=2(2a₀+3)+3.
Regrouping the terms, we get a₄=141, where a₀=6.

6. The solution to the recurrence relation a_n=a_n-1+2n, with initial term a₀=2 are _________
a) 4n+7
b) 2(1+n)
c) 3n²
d) 5*(n+1)/2

Answer: b
Clarification: When n=1, a₁=a₀+2. By substitution we get, a₂=a₁+2 ⇒ a₂=(a₀+2)+2 and so on. So the solution to the recurrence relation, subject to the initial condition should be a_n=2+2n=2(1+n).

7. Determine the solution for the recurrence relation b_n=8b_n-1−12b_n-2 with b₀=3 and b₁=4.
a) 7/2*2ⁿ−1/2*6ⁿ
b) 2/3*7ⁿ-5*4ⁿ
c) 4!*6ⁿ
d) 2/8ⁿ

Answer: a
Clarification: Rewrite the recurrence relation b_n-8b_n-1+12b_n-2=0. Now from the characteristic equation: x²−8x+12=0 we have x: (x−2)(x−6)=0, so x=2 and x=6 are the characteristic roots. Therefore the solution to the recurrence relation will have the form: b_n=b2ⁿ+c6ⁿ. To find b and c, set n=0 and n=1 to get a system of two equations with two unknowns: 3=b2⁰+c6⁰=b+c, and 4=b2¹+c6¹=2b+6c. Solving this system gives c=-1/2 and b=7/2. So the solution to the recurrence relation is, b_n=7/2*2ⁿ−1/2*6ⁿ.

8. What is the solution to the recurrence relation a_n=5a_n-1+6a_n-2?
a) 2n²
b) 6n
c) (3/2)n
d) n!*3

Answer: b
Clarification: Check for the left side of the equation with all the options into the recurrence relation. Then, we get that 6n is the required solution to the recurrence relation a_n=5a_n-1 + 6a_n-2.

9. Determine the value of a2 for the recurrence relation a_n = 17a_n-1 + 30n with a₀=3.
a) 4387
b) 5484
c) 238
d) 1437

Answer: d
Clarification: When n=1, a₁=17a₀+30, Now a₂=17a₁+30*2. By substitution, we get a₂=17(17a₀+30)+60. Then regrouping the terms, we get a₂=1437, where a₀=3.

10. Determine the solution for the recurrence relation a_n = 6a_n-1−8a_n-2 provided initial conditions a₀=3 and a₁=5.
a) a_n = 4 * 2ⁿ – 3ⁿ
b) a_n = 3 * 7ⁿ – 5*3ⁿ
c) a_n = 5 * 7ⁿ
d) a_n = 3! * 5ⁿ

Answer: b
Clarification: The characteristic polynomial is x²−6x+8. By solving the characteristic equation, x²−6x+8=0 we get x=2 and x=4, these are the characteristic roots. Therefore we know that the solution to the recurrence relation has the form a_n=a*2ⁿ+b*4ⁿ, for some constants a and b. Now, by using the initial conditions a₀ and a₁ we have: a=7/2 and b=-1/2. Therefore the solution to the recurrence relation is: a_n = 4 * 2ⁿ – 1*3ⁿ = 7/2 * 2ⁿ – 1/2*3ⁿ.

Discrete Mathematics Multiple Choice Questions on “Graphs – Diagraph”.

1. A directed graph or digraph can have directed cycle in which ______
a) starting node and ending node are different
b) starting node and ending node are same
c) minimum four vertices can be there
d) ending node does not exist

Answer: b
Clarification: If the start node and end node are same in the path of a graph then it is termed as directed cycle i.e, c₀ = c_n. For instance, a c b a is a simple cycle in which start and end nodes are same(a). But, a c b b a is not a simple cycle as there is a loop <b,b>.

2. Let, D = <A, R> be a directed graph or digraph,then D’ = <A’, R’> is a subgraph if ___________
a) A’ ⊂ A and R’ = R ∩ (A’ x A’)
b) A’ ⊂ A and R ⊂ R’ ∩ (A’ x A’)
c) R’ = R ∩ (A’ x A’)
d) A’ ⊆ A and R ⊆ R’ ∩ (A’ x A’)

Answer: a
Clarification: A directed graph or digraph is an ordered pair D<A, R> where A(is a set of nodes of D) is a set and R(the elements of R are the arcs of D) is a binary relation on A. The relation R is called the incidence relation on D. Now, a digraph is a subgraph of D if i)A’ ⊂ A and ii)R’ = R ∩ (A’ x A’). If D’ D, D’ is a proper subgraph of D.

3. The graph representing universal relation is called _______
a) complete digraph
b) partial digraph
c) empty graph
d) partial subgraph

Answer: a
Clarification: Consider, A is a graph with vertices {a, b, c, d} and the universal relation is A x A. The graph representing universal relation is called a complete graph and all ordered pairs are present there.

4. What is a complete digraph?
a) connection of nodes without containing any cycle
b) connecting nodes to make at least three complete cycles
c) start node and end node in a graph are same having a cycle
d) connection of every node with every other node including itself in a digraph

Answer: d
Clarification: Every node should be connected to every other node including itself in a digraph is the complete digraph. Now, graphs are connected, strongly connected and disconnected

5. Disconnected components can be created in case of ___________
a) undirected graphs
b) partial subgraphs
c) disconnected graphs
d) complete graphs

Answer: c
Clarification: By the deletion of one edge from either connected or strongly connected graphs the graph obtained is termed as a disconnected graph. It can have connected components separated by the deletion of the edges. The edge that has to be deleted called cut edge.

6. A simple graph can have _______
a) multiple edges
b) self loops
c) parallel edges
d) no multiple edges, self-loops and parallel edges

Answer: d
Clarification: If a graph say G = <V, E> has no parallel or multiple edges and no self loops contained in it is called a simple graph. An undirected graph may have multiple edges and self-loops.

7. Degree of a graph with 12 vertices is _______
a) 25
b) 56
c) 24
d) 212

Answer: c
Clarification: Number of edges incident on a graph is known as degree of a vertex. Sum of degrees of each vertex is called total degree of the graph. Total degree = 2 * number of vertices. So, if there are 24 vertices then total degree is 24.

8. In a finite graph the number of vertices of odd degree is always ______
a) even
b) odd
c) even or odd
d) infinite

Answer: a
Clarification: In any finite graph, sum of degree of all the vertices = 2 * number of edges.
Sum of degree of all the vertices with even degree + sum of degree of all the vertices with odd degree = 2 * number of edges. Now, even number + sum of degree of all the vertices with odd degree = even number. It is possible if and only if number of odd degree vertices are even.

9. An undirected graph has 8 vertices labelled 1, 2, …,8 and 31 edges. Vertices 1, 3, 5, 7 have degree 8 and vertices 2, 4, 6, 8 have degree 7. What is the degree of vertex 8?
a) 15
b) 8
c) 5
d) 23

Answer: b
Clarification: Vertices 1, 3, 5, 7 have degree 8 and vertices 2, 4, 6, 8 have degree 7. By definition, sum of degree= 2 * No of edges
Let x = degree of vertex 8
8 + 7 + 8 + 7 + 8 + 7 + 8 + x = 2 * 31
53 + x = 61
x = 8
Hence, degree of vertex 8 is 8.

10. G is an undirected graph with n vertices and 26 edges such that each vertex of G has a degree at least 4. Then the maximum possible value of n is ___________
a) 7
b) 43
c) 13
d) 10

Answer: c
Clarification: Let m be min degree and M be a max degree of a graph, then m ≤ 2E/V ≤ M. Here, m=4, E=26, v=?
So, 4 ≤ (2*26)/V
V ≤ (52/4)
V ≤ 13 ⇒ V = 13.

Discrete Mathematics Multiple Choice Questions on “Boolean Functions”.

1. What is the use of Boolean identities?
a) Minimizing the Boolean expression
b) Maximizing the Boolean expression
c) To evaluate a logical identity
d) Searching of an algebraic expression

Answer: a
Clarification: Boolean identities are used for minimizing the Boolean expression and transforming into an equivalent expression.

2. _________ is used to implement the Boolean functions.
a) Logical notations
b) Arithmetic logics
c) Logic gates
d) Expressions

Answer: c
Clarification: To implement a Boolean function logic gates are used. Basic logic gates are AND, OR and NOT.

3. Inversion of single bit input to a single bit output using _________
a) NOT gate
b) NOR gate
c) AND gate
d) NAND gate

Answer: a
Clarification: A NOT gate is used to invert a single bit input (say A) to a single bit of output (~A).

4. There are _________ numbers of Boolean functions of degree n.
a) n
b) 2^(2*n)
c) n³
d) n^(n*2)

Answer: b
Clarification: There are 2n different n-tuples of 0’s and 1’s. A Boolean function is an assignment of 0’s or 1’s to each of these 2 n different n-tuples. Hence, there are 2^(2*n) different Boolean functions.

5. A _________ is a Boolean variable.
a) Literal
b) String
c) Keyword
d) Identifier

Answer: a
Clarification: A literal is a Boolean variable or its complement. A maxterm is a sum of n literals and a minterm is a product of n literals.

6. Minimization of function F(A,B,C) = A*B*(B+C) is _________
a) AC
b) B+C
c) B`
d) AB

Answer: d
Clarification: AB(B+C)
= ABB + ABC [Applying distributive rule]
= AB + ABC [Applying Idempotent law]
= AB (1+C)
= AB*1 [As, 1+C=1]
= AB.

7. The set for which the Boolean function is functionally complete is __________
a) {*, %, /}
b) {., +, -}
c) {^, +, -}
d) {%, +, *}

Answer: b
Clarification: A Boolean function is represented by using three operators ., +, -. We can find a smaller set of functionally complete operators if one of the three operators of this set can be expressed in terms of the other two.

8. (X+Y`)(X+Z) can be represented by _____
a) (X+Y`Z)
b) (Y+X`)
c) XY`
d) (X+Z`)

Answer: a
Clarification: (X+Y`) (X+Z)
= XX + XZ + XY`+ Y`Z
= X + XZ + XY`+ Y`Z
= X (1+Z) + XY`+ Y`Z
= X.1 + XY`+ Y`Z
= X (1+Y`) + Y`Z
= X + Y`Z.

9. __________ is a disjunctive normal form.
a) product-of-sums
b) product-of-subtractions
c) sum-of-products
d) sum-of-subtractions

Answer: c
Clarification: The sum of minterms that represents the function is called the sum-of-products expansion or the disjunctive normal form. A Boolean sum of minterms has the value 1 when exactly one of the minterms in the sum has the value 1. It has the value 0 for all other combinations of values of the variables.

10. a ⊕ b = ________
a) (a+b)(a`+b`)
b) (a+b`)
c) b`
d) a` + b`

Answer: a
Clarification: a ⊕ b
= a`b + ab`
= a`b+aa` + bb` + ab` [As, a*a` = 0 and b*b` = 0]
= a`(a+b) + b`(a+b)
= (a+b)(a`+b`).

Discrete Mathematics Multiple Choice Questions on “Logics – Logical Equivalences”.

1. The compound propositions p and q are called logically equivalent if ________ is a tautology.
a) p ↔ q
b) p → q
c) ¬ (p ∨ q)
d) ¬p ∨ ¬q

Answer: a
Clarification: Definition of logical equivalence.

2. p → q is logically equivalent to ________
a) ¬p ∨ ¬q
b) p ∨ ¬q
c) ¬p ∨ q
d) ¬p ∧ q

Answer: c
Clarification: (p → q) ↔ (¬p ∨ q) is tautology.

3. p ∨ q is logically equivalent to ________
a) ¬q → ¬p
b) q → p
c) ¬p → ¬q
d) ¬p → q

Answer: d
Clarification: (p ∨ q) ↔ (¬p → q) is tautology.

4. ¬ (p ↔ q) is logically equivalent to ________
a) q↔p
b) p↔¬q
c) ¬p↔¬q
d) ¬q↔¬p

Answer: b
Clarification: ¬(p↔q)↔(p↔¬q) is tautology.

5. p ∧ q is logically equivalent to ________
a) ¬ (p → ¬q)
b) (p → ¬q)
c) (¬p → ¬q)
d) (¬p → q)

Answer: a
Clarification: (p ∧ q) ↔ (¬(p → ¬q)) is tautology.

6. Which of the following statement is correct?
a) p ∨ q ≡ q ∨ p
b) ¬(p ∧ q) ≡ ¬p ∨ ¬q
c) (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
d) All of mentioned

Answer: d
Clarification: Verify using truth table, all are correct.

7. p ↔ q is logically equivalent to ________
a) (p → q) → (q → p)
b) (p → q) ∨ (q → p)
c) (p → q) ∧ (q → p)
d) (p ∧ q) → (q ∧ p)

Answer: c
Clarification: (p ↔ q) ↔ ((p → q) ∧ (q → p)) is tautology.

8. (p → q) ∧ (p → r) is logically equivalent to ________
a) p → (q ∧ r)
b) p → (q ∨ r)
c) p ∧ (q ∨ r)
d) p ∨ (q ∧ r)

Answer: a
Clarification: ((p → q) ∧ (p → r)) ↔ (p → (q ∧ r)) is tautology.

9. (p → r) ∨ (q → r) is logically equivalent to ________
a) (p ∧ q) ∨ r
b) (p ∨ q) → r
c) (p ∧ q) → r
d) (p → q) → r

Answer: c
Clarification: ((p → r) ∨ (q → r)) ↔ ((p ∧ q) → r) is tautology.

10. ¬ (p ↔ q) is logically equivalent to ________
a) p ↔ ¬q
b) ¬p ↔ q
c) ¬p ↔ ¬q
d) ¬q ↔ ¬p

Answer: a
Clarification: (¬ (p ↔ q)) ↔ (p ↔ ¬q) is tautology.