MAT2051 Discrete Mathematics -Capella MAT2051 Unit 10 Quiz 5 Latest 2020
Unit 10 Quiz 5
Question 1Given an unordered list of n numbers, what algorithm would you use to sort it, and what is the worst-case runtime of
...
MAT2051 Discrete Mathematics -Capella MAT2051 Unit 10 Quiz 5 Latest 2020
Unit 10 Quiz 5
Question 1Given 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 2Given 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 3Which 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 4How many six-bit strings begin with 100?
Answers:
a. 4.
b. 8.
c. 32.
d. 16.
Question 5If 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 6If 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:
Base case:
Prove true for n = 1: 51-1=5-1=4 is divisible by 4.
Assumption Step:
Assume true for value n.
Assume 5n-1 is divisible by 4. Therefore we can write 5n-1 = 4*k for some constant k.
Final step:
Prove true for value n+1.
5(n+1)-1 = 5n*5-1 = 5n*(4+1)-1 = 4*5n+(5n-1)
Substituting assumption step 5n-1 = 4*k:
5(n+1)-1 = 4*5n+(5n-1) = 4*5n+(4*k) = 4*(5n+k).
5(n+1)-1 is divisible by 4.
This concludes our inductive proof that 5n-1 is divisible by 4.
Question 7Which of the following is not a proof method?
Answers:
a. Existence proof.
b. Proof by contradiction.
c. Proof by converse.
d. Direct Proof.
Question 8What 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:
Unit 10 Quiz, Question 9. The answers are tables, they are noted here in order (matched with the letter.) [D]
Answers:
a. 2
10
14
0
1
2
3
4
b.
2
13
9
0
1
2
3
4
c.
2
10
14
0
1
2
3
4
d.
10
2,14
0
1
2
3
4
Question 10Represent 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 11Assume 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 12How 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 13 Given 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 14Given 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 15Given 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 16Given 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 20What 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 23Given 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 24Which 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.
[Show More]
 (1).png)
