Capella MAT2051 Unit 10 Quiz Latest 2019 October

MAT2051 Discrete Mathematics

Unit 10 Quiz

Question 1 Given an unordered list of n numbers, what algorithm would you use to sort it, and what is the worst-case runtime of the algorithm?

Answers:             

a. Tournament sort, O(n log n).

b. Tournament sort, O(n).

c. Prim’s Algorithm, O(n log n).

d. Prim’s Algorithm, O(n * n).

Question 2 Given a graph with n vertices, what is the minimum number of edges needed such that the graph is connected?

Answers:             

a. n.

b. n – 1.

c. n * n.

d. n log n.

Question 3          Which is a minimal spanning tree of the following graph:

Graph A-E.[D]

Answers:             

a. A-B-D-E-C.

b. A-D-E-C-B.

c. A-B-D.

d. There is no minimal spanning tree.

Question 4 How many six-bit strings begin with 100?

Answers:             

a. 4.

b. 8.

c. 32.

d. 16.

Question 5          If you select 5 microprocessors from 100 microprocessors, where 30 of the 100 are defective, what is the probability that you select no defective processors?

Answers:             

a. C(100, 10)/C(30, 5).

b. C(70, 5)/C(100, 5).

c. C(100, 5).

d. C(100, 5)/C(70, 5).

Question 6 If using induction to prove that 5n 1 is divisible by 4 for all n e 1, provide the base case, the assumption step, and a final step that can be used to prove for all n.

Note: Please use ^ for exponent. For example, 3 ^ 2 = 9

Selected Answer:             

Let P(n) be the statement 5^n-1 is divisible by 4

We have to prove the result by mathematical induction on n.

When n = 1, then 5^1-1= 5-1 = 4 is divisible by 4

Therefore P(1) is true.

Assume the result for P(k).

Then 5^k-1= 4m for some integer m……… (1)

consider 5^(k+1)- 1 = 5*5^k-1= 5(4m+1)-1, From (1)

= 20m +4

= 4(5m-1)

Question 7          Which of the following is not a proof method?

Answers:             

a. Existence proof.

b. Proof by contradiction.

c. Proof by converse.

d. Direct Proof.

Question 8          What is the cardinality of the set X = {1,5,3,8,10}?

Answers:             

a. 5.

b. 1.

c. 10.

d. 27.

Question 9 Given a hash function h(n) = n mod 5, what would a computer s memory cells look like if we were to input values 2, 9, and 13:

Question 10        Represent the following database as n-ary tuples:

Database Table.[D]

Answers:             

a. {(Joe Smith, Smith21,1), (Jane Doe, Jdoe1, 1), (Tim Thomas, TimT, 5)}.

b. {(Joe Smith, Jane Doe, Tim Thomas), (Smith21, Jdoe1, TimT), (1, 1, 5)}.

c. {(Joe, Smith, Smith21,1), (Jane, Doe, Jdoe1, 1), (Tim, Thomas, TimT, 5)}.

d. {(Joe, Smith, Jane, Doe, Tim, Thomas), (Smith21, Jdoe1, TimT), (1, 1, 5)}.

Question 11        Assume A is the universal quantifier, E is the existential quantifier and ~ is the symbol for NOT. Let P(x) = 2 x>3x. Assume that x can be any real number. Which of the following statements is true?

Answers:             

a. Ex P(x).

b. Ax P(x).

c. Ax ~P(x).

d. None of the above.

Question 12 How many strings of length 3 are possible (without repetition) given a set X = {a, b, c, d}.

Answers:             

a. 6.

b. 8.

c. 24

d. 1,248.

Question 13Given the graph below, what is (A, D, C, D, B)?

Graph A-E.[D]

Answers:             

a. Simple path.

b. Cycle.

c. Simple cycle.

d. None of the above.

Question 14        Given the graph below, which of the following is a Hamiltonian cycle?

Graph A-E.[D]

Answers:             

a. (C, E, D, A, B, C)

b. (A, D, B, C, E, D, A).

c. (B, C, E, D, B, C, B).

d. (C, E, D, A, C).

Question 15        Given the graph below, what is the total weight of the shortest weighted path from A to E?

Graph A-E.[D]

Answers:             

a. 8.

b. 5.

c. 4.

d. 3.

Question 16 Given a graph with n vertices, what is the minimum number of edges needed to make the graph connected?

Answers:             

a. n.

b. n – 1.

c. n * n.

d. n log n.

Question 17How many times does the computer print the string “Good bye”?

i = 2

while (i < 7) {

print (“Good bye”)

i = i + 1}

Answers:             

a. 4.

b. 5.

c. 3.

d. 6.

Question 18Which of the following algorithm computation times is O(n)?

Answers:             

a. 2n – 5.

b. n * log(n).

c. n * n + n.

d. None of the above.

Question 19If each of the following describes the run time of an algorithm, which of the following has the longest worst-case run time?

Answers:             

a. O(nlog(n)).

b. O(n).

c. O(n/2).

d. O(n * n).

Question 20 What does the following algorithm return?

f(n){

if (n< 2)

return 1

else

return f(n – 1) + n

Answers:             

a. n!

b. The maximum divisor of n.

c. n + (n – 1) + (n – 2) + . . . + 1.

d. n – 2.

Question 21In terms of n, what is the closest-fit worst-case time complexity of the following algorithm?

f(n){

if (n< 2)

return 1

else

return f(n – 1) * n

Answers:             

a. O(n).

b. O(log(n)).

c. O(n!).

d. None of the above.

Question 22Note that in analysis of algorithms, time complexity is typically measured in terms of the size of the input and not the input values. If n is a single number, then its binary string representation can be represented using approximately m bits (the size of the input), where m = log_2(n). Therefore, the maximum value that can be expressed in m bits is n = O(exp(m)). In terms of m, what is the closest-fit worst-case time complexity of following algorithm?

f(n){

if (n< 2)

return 1

else

return f(n – 1) * n

Answers:             

a. O(m).

b. O(log(m)).

c. O(exp(m)).

d. None of the above.

Question 23        Given the graph below, which algorithm is best used to find a shortest path from A to E?

Graph A-E.[D]

Answers:             

a. Dijkstra’s.

b. Tournament sort.

c. Prim’s.

d. Bubble sort.

Question 24  Which of the following problems cannot be solved using graphs and graph-based algorithms?

Answers:             

a. Matching problem.

b. Sorting of a list of numbers.

c. Traveling salesman problem.

d. None of the above.

Question 25 Which of the following problems can always be solved using trees and tree-based algorithms?

Answers:             

a. Maximum flow problem.

b. Minimum cut problem.

c. Sorting of a list of numbers.

d. All of the above.