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.

250+ TOP MCQs on Relations – Partial Orderings and Answers

Discrete Mathematics Multiple Choice Questions on “Relations – Partial Orderings”.

1. Let a set S = {2, 4, 8, 16, 32} and <= be the partial order defined by S <= R if a divides b. Number of edges in the Hasse diagram of is ______
a) 6
b) 5
c) 9
d) 4

Answer: b
Clarification: Hasse Diagram is:

          32   	
          /  	
       16  	
       / 	
     8  
   /     
  2     4

So, the number of edges should be: 4.

2. The less-than relation, <, on a set of real numbers is ______
a) not a partial ordering because it is not asymmetric and irreflexive equals antisymmetric
b) a partial ordering since it is asymmetric and reflexive
c) a partial ordering since it is antisymmetric and reflexive
d) not a partial ordering because it is not antisymmetric and reflexive

Answer: a
Clarification: Relation less than a set of real numbers is not antisymmetric and reflexive. Relation is not POSET because it is irreflexive. Again, aRb != bRa unless a=b and so it is antisymmetric. A relation may be ‘not asymmetric and not reflexive but still antisymmetric, as {(1,1) (1,2)}. So, the relation is not a partial ordering because it is not asymmetric and irreflexive equals antisymmetric.

3. If the longest chain in a partial order is of length l, then the partial order can be written as _____ disjoint antichains.
a) l2
b) l+1
c) l
d) ll

Answer: c
Clarification: If the length of the longest chain in a partial order is l, then the elements in the POSET can be partitioned into l disjoint antichains.

4. Suppose X = {a, b, c, d} and π1 is the partition of X, π1 = {{a, b, c}, d}. The number of ordered pairs of the equivalence relations induced by __________
a) 15
b) 10
c) 34
d) 5

Answer: b
Clarification: The ordered pairs of the equivalence relations induced = {(a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b), (c,c), (d,d)}. Poset -> equivalence relations = each partition power set – Φ.

5. A partial order P is defined on the set of natural numbers as follows. Here a/b denotes integer division. i)(0, 0) ∊ P. ii)(a, b) ∊ P if and only if a % 10 ≤ b % 10 and (a/10, b/10) ∊ P. Consider the following ordered pairs:
i. (101, 22) ii. (22, 101) iii. (145, 265) iv. (0, 153)
The ordered pairs of natural numbers are contained in P are ______ and ______
a) (145, 265) and (0, 153)
b) (22, 101) and (0, 153)
c) (101, 22) and (145, 265)
d) (101, 22) and (0, 153)

Answer: d
Clarification: For ordered pair (a, b), to be in P, each digit in a starting from unit place must not be larger than the corresponding digit in b. This condition is satisfied by options (iii) (145, 265) => 5 ≤ 5, 4 < 6 and 1 < 2; (iv) (0, 153) => 0 < 3 and no need to examine further.

6. The inclusion of ______ sets into R = {{1, 2}, {1, 2, 3}, {1, 3, 5}, {1, 2, 4}, {1, 2, 3, 4, 5}} is necessary and sufficient to make R a complete lattice under the partial order defined by set containment.
a) {1}, {2, 4}
b) {1}, {1, 2, 3}
c) {1}
d) {1}, {1, 3}, {1, 2, 3, 4}, {1, 2, 3, 5}

Answer: c
Clarification: A lattice is complete if every subset of partial order set has a supremum and infimum element. For example, here we are given a partial order set R. Now it will be a complete lattice if whatever be the subset we choose, it has a supremum and infimum element. Here relation given is set containment, so supremum element will be just union of all sets in the subset we choose. Similarly, the infimum element will be just an intersection of all the sets in the subset we choose. As R now is not complete lattice, because although it has a supremum for every subset we choose, but some subsets have no infimum. For example, if we take subset {{1, 3, 5}, {1, 2, 4}}, then intersection of sets in this is {1}, which is not present in R. So clearly, if we add set {1} in R, we will solve the problem. So adding {1} is necessary and sufficient condition for R to be a complete lattice.

7. Consider the ordering relation a | b ⊆ N x N over natural numbers N such that a | b if there exists c belong to N such that a*c=b. Then ___________
a) | is an equivalence relation
b) It is a total order
c) Every subset of N has an upper bound under |
d) (N,|) is a lattice but not a complete lattice

Answer: d
Clarification: A set is called lattice if every finite subset has a least upper bound and greatest lower bound. It is termed as a complete lattice if every subset has a least upper bound and greatest lower bound. As every subset of this will not have LUB and GLB so (N,|) is a lattice but not a complete lattice.

8. Consider the set N* of finite sequences of natural numbers with a denoting that sequence a is a prefix of sequence b. Then, which of the following is true?
a) Every non-empty subset of has a greatest lower bound
b) It is uncountable
c) Every non-empty finite subset of has a least upper bound
d) Every non-empty subset of has a least upper bound

Answer: a
Clarification: Consider any sequence like “45, 8, 7, 2” – it can have many (infinite) least upper bounds like “45, 8, 7, 2, 5”, “45, 8, 7, 2, 1” and so on but it can have only 1 greatest lower bound – “45, 8, 7” because we are using the prefix relation. So, every non-empty subset has a greatest lower bound.

9. A partial order ≤ is defined on the set S = {x, b1, b2, … bn, y} as x ≤ bi for all i and bi ≤ y for all i, where n ≥ 1. The number of total orders on the set S which contain the partial order ≤ is ______
a) n+4
b) n2
c) n!
d) 3

Answer: c
Clarification: To make this partial order a total order, we need the relation to hold for every two element of the partial order. Currently, there is no relation between any bi and bj. So, for every bi and bj, we have to add either (bi, bj) or (bj, bi) in total order. So, this translates to giving an ordering for n elements between x and y, which can be done in n! ways.

10. Let (A, ≤) be a partial order with two minimal elements a, b and a maximum element c. Let P:A –> {True, False} be a predicate defined on A. Suppose that P(a) = True, P(b) = False and P(a) ⇒ P(b) for all satisfying a ≤ b, where ⇒ stands for logical implication. Which of the following statements cannot be true?
a) P(x) = True for all x S such that x ≠ b
b) P(x) = False for all x ∈ S such that b ≤ x and x ≠ c
c) P(x) = False for all x ∈ S such that x ≠ a and x ≠ c
d) P(x) = False for all x ∈ S such that a ≤ x and b ≤ x

Answer: d
Clarification: Here, maximum element is c and so c is of a higher order than any other element in A. Minimal elements are a and b: No other element in A is of lower order than either a or b.
We are given P(a) = True. So, for all x such that a≤x, P(x) must be True. We do have at least one such x, which is c as it is the maximum element. So, P(x) = False for all x ∈ S such that a ≤ x and b ≤ x -> cannot be true. P(x) = True for all x S such that x ≠ b -> can be True as all elements mapped to TRUE doesn’t violate the given implication. P(x) = False for all x ∈ S such that x ≠ a and x ≠ c -> can be True if a is related only to c. P(x) = False for all x ∈ S such that b ≤ x and x ≠ c -> can be True as b≤x ensures x≠a and for all other elements P(x) can be False without violating the given implication.

250+ TOP MCQs on Spanning Trees and Answers

Discrete Mathematics Multiple Choice Questions on “Spanning Trees”.

1. Spanning trees have a special class of depth-first search trees named _________
a) Euclidean minimum spanning trees
b) Tremaux trees
c) Complete bipartite graphs
d) Decision trees

Answer: b
Clarification: A tremaux tree of an undirected graph G is a spanning tree of G which is rooted at one of its vertices with the property that every two adjacent vertices in G are related to each other as an ancestor and descendant in the tree.

2. If the weight of an edge e of cycle C in a graph is larger than the individual weights of all other edges of C, then that edge ________
a) belongs to an minimum spanning tree
b) cannot belong to an minimum spanning tree
c) belongs to all MSTs of the graph
d) can not belong to the graph

Answer: b
Clarification: For any cycle C in the graph, if the weight of an edge e of C is larger than the individual weights of all other edges of C, then this edge cannot belong to an MST.

3. For every spanning tree with n vertices and n edges what is the least number of different Spanning trees can be formed?
a) 2
b) 5
c) 3
d) 4

Answer: c
Clarification: If graph is connected and has ‘n’ edges, there will be exactly one cycle, if n vertices are there. A different spanning tree can be constructed by removing one edge from the cycle, one at a time. The minimum cycle length can be 3. So, there must be at least 3 spanning trees in any such Graph. Consider a Graph with n = 4, then 3 spanning trees possible at maximum (removing edges of cycle one at a time, alternatively). So, any Graph with minimum cycle length ‘3’ will have at least 3 spanning trees.

4. Time complexity of Prim’s algorithm is _________
a) O((V+E)logV)
b) O(E+V)
c) O(E)
d) O(V+1)

Answer: a
Clarification: In Prim’s Algorithm, we will start with an arbitrary node (take any point to start) and mark it. In each iteration, a new vertex is marked that is adjacent to the one that we have already marked. Each vertex is inserted in the priority queue only once and insertion in priority queue take logarithmic time. Hence, the time complexity of Prim’s Algorithm is O((V+E)logV).

5. What is the time complexity of Kruskal’s algorithm?
a) O(ElogV)
b) O(V+logE)
c) O(E+1)
d) O(V2)

Answer: a
Clarification: In Kruskal’s algorithm, at each iteration, we will select the edge with the lowest weight. So, we will start with the lowest weighted edge first. After that we will select the second lowest weighted edge. In Kruskal’s algorithm, most time consuming operation is sorting because the total complexity of the Disjoint-Set operations will be O(ElogV) and it is the overall Time Complexity of the algorithm.

6. An immediate application of minimum spanning tree ______
a) gesture analysis
b) handwriting recognition
c) fingerprint detection
d) soft computing

Answer: b
Clarification: Minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees. It is used in network designing, in the algorithms predicting the travelling salesman problem,multi-terminal minimum cut problem and minimum-cost weighted perfect matching. It can also used in Handwriting recognition and image segmentation.

6. If minimum cost edge of a graph is unique, then that edge will be added to any MST. Choose the correct option.
a) false
b) maximum cost edge is added
c) true
d) minimum cost edge need not be unique

Answer: c
Clarification: If the edge was not included in the MST, removing any of the (larger cost) edges in the cycle formed after adding e to the MST, would yield a spanning tree of smaller weight. Thus, if the minimum cost edge e of a graph is unique, then this edge is included in any MST.

7. A complete undirected graph of n nodes can have maximum ______ spanning trees.
a) nn+1
b) nn-2
c) (frac{n(n+1)}{2})
d) n

Answer: b
Clarification: The spanning tree does not contain any cycle. If a spanning tree has n nodes, there are n-1 edges. A complete graph can have a maximum of nn-2 number of spanning trees.

8. The spanning tree will be maximally acyclic if ____________
a) one additional edge makes a cycle in the tree
b) two additional edges makes a cycle in the tree
c) removing one edge makes the tree cycle free
d) removing two edges make the tree cycle free

Answer: a
Clarification: A connected graph G can have more than one spanning tree. Removing one edge from the spanning tree will make the graph disconnected and the spanning tree is minimally connected. Adding one edge to the spanning tree will create a circuit or loop and the spanning tree is maximally acyclic.

9. In a maximum spanning tree the weighted graph is of _______
a) maximum number of edges
b) maximum number of cyclic trees
c) minimum number of vertices
d) maximum weight

Answer: d
Clarification: A maximum spanning tree can be computed by negating the weights for each edge and applying Kruskal’s algorithm. Thus, it is a spanning tree of a weighted graph having maximum weight assigned to all the edges.

10. Prim’s algorithm can be implemented using _______
a) a stack data structure
b) radix sort
c) priority queue data structure
d) bubble sort

Answer: c
Clarification: The time complexity of Prim’s algorithm depends on the data structures used for the graph and for ordering the edges by weight, which can be done using a priority queue. In general, a priority queue will be quicker at finding the vertex in the spanning tree with minimum cost. The choice of data structures for implementation will lead to varying time complexity.