MAT2051 Unit 10 Quiz 5 Latest 2020 ; Complete solution guide, Capella University.

Document Content and Description Below

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 wo... rst-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]

Last updated: 2 years ago

Preview 1 out of 18 pages