27 Dec Question 25 Which of the following

MAT2051 Discrete Mathematics

Unit 2 Quiz

Question 1 What is a set?

Answers:

a. An unordered collection of objects.

b. An ordered collection of objects.

c. The study of reasoning.

d. A partition of numbers.

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

Answers:

a. 5.

b. 1.

c. 10.

d. 27.

Question 3 What value replaces ? in the following truth table?

Answers:

a. 0.

b. 1.

c. Cannot solve with the given information.

d. Can be either 0 or 1.

Question 4 Let:

P: Jerry receives a scholarship.

Q: Jerry goes to college.

Assume the statement P → Q is true.

If Jerry does not go to college, did he receive his scholarship?

Answers:

a. Yes, because the converse of the statement is true.

b. No, because the contrapositive of the statement is true.

c. There is not enough information.

d. Can be either.

Question 5 What is deductive reasoning?

Answers:

a. A hypothesis together with a conclusion.

b. Valid arguments of a hypothesis.

c. The process of drawing a conclusion from a sequence of propositions.

d. A simplification of the rules of inference.

Question 6 Assume that ~, v, and ^ are the NOT, OR, and AND symbols, respectively. Use a truth table to determine if the following Boolean equation ~x1 v (x2 ^ x1):

Answers:

a. Is functionally identical to an AND gate.

b. Is functionally identical to an OR gate.

c. Is not like an AND or an OR gate.

d. Is a NOT gate.

Question 7 The function f(x) = x + 3 is best described as:

Onto the reals.

Answers:

a. One-to-one with the reals.

b. Onto the reals.

c. Is a bijection with the reals.

d. Is neither one-to-one nor onto.

Question 8 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, 10, and 14?

Unit 2 Quiz, Question 8. The answers are tables, they are noted here in order (matched with the letter.)[D]

Answers:

a. a.

b. b.

c. c.

d. d.

Question 9 How many strings of length 2 can be created from the set X = {a, b, c} without replacement (without replacement simply means that you cannot use the same element more than once).

Answers:

a. 6.

b. 8.

c. 24.

d. 12.

e. 16.

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)}.

MAT2051 Discrete Mathematics

Unit 4 Quiz

Question 1 How many different eight-bit strings begin with 100?

Answers:

a. 4.

b. 32.

c. 64.

d. 16.

Question 2 How many strings can be formed using the letters in the word router (that is, R-O-U-T-E-R)?

Answers:

a. 6!/2!

b. C(6, 1).

c. (6 1)!

d. C(1, 6).

Question 3 There are 100 processors, 30 of which are defective. If you select 20 microprocessors from these 100 microprocessors, what is the probability that you select no defective processors?

Answers:

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

b. C(100, 20).

c. C(100, 20)/C(70, 20).

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

Question 4 What is the probability of drawing a queen from a standard deck of cards?

Answers:

a. 2/52.

b. 10%.

c. 8/52.

d. 4/52.

Question 5 Assume the probability of having a boy or a girl is the same. If a family has five children, what is the probability that they are all boys?

Selected Answer:

a. 1/32.

b. 1/16.

c. 1/2 + 1/2 + 1/2 + 1/2 + 1/2.

d. 1/2.

Question 6 If using induction to prove that 5n 1 is divisible by 4 for all n e 1, which of the four choices best represents the base case, the assumption step, and a final step that can be used to prove for all n?

Answers:

a. 50 – 1,

5m – 1 is divisible by 4 for some value m < 1, 4 * 5m+1 + 5m+1 1 b. 51 - 1, 5m 1 is divisible by 4 for some value m > 1,

4 * 5m-1 + 5m-1 – 1

c. 51 – 1,

5m – 1 is divisible by 4 for some value m > 1,

4 * 5m + 5m – 1

d. 51 1,

-5m + 1 is divisible by 4 for some value m > 1,

Question 7 Two dice are rolled. What is the probability of rolling double sixes or double fives?

Answers:

a. 1/18.

b. 1/36.

c. 2/3.

d. 1/9.

Question 8 Suppose a microprocessor is chosen at random from a collection of 100. Assume 20 are Intels and 80 are AMDs. Also assume that 10 of the Intels are 2.0 GHz. What is the probability that the selected microprocessor is 2.0 GHz given that it is an Intel?

Answers:

a. 1/2.

b. 1/5.

c. 3/10.

d. 2/3.

Question 9 If m and n are even numbers, is y = m + n an even number?

Answers:

a. Yes.

b. No.

c. Not enough information.

d. None of the above.

Question 10 Assume that –> is IMPLICATION and ~ is NOT. Given that the following statements are true, what can be concluded via resolution?

P –> Q.

~Q.

Answers:

a. P.

b. Q.

c. ~P.

d. Q P.

MAT2051 Discrete Mathematics

Unit 6 Quiz

• Question 1 How many times does the computer print the string “Hello”?

i = 2

while (i < 4) { print ("Hello") i = i + 1}: Answers: a. 1. b. 2. c. 3. d. 4. • Question 2 Which of the following is O(n)? Answers: a. 3n + 1. b. n * log(n). c. n * n + n. d. None of the above. • Question 3 If each of the following describes the run time of an algorithm, which of the following could have the longest run time? Answers: a. O(nlog(n)). b. O(n!). c. O(n/2). d. O(n * n). • Question 4 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 - 1)! d. n 2. • Question 5 Given that S_n denotes the number of n-bit strings that do not contain the pattern 00, what are the initial conditions? Answers: a. S_1 = 2, S_2 =3. b. S_1 = 1, S_2 =2. c. S_1 = 0, S_2 =2. d. None of the above. • Question 6 Given that S_n denotes the number of n-bit strings that do not contain the pattern 00, what is the recurrence relation? Answers: a. S_n = S_{n - 1} + S_{n - 2}. b. S_n = S_{n - 1} + 1. c. S_n = S_{n - 1} + 2. d. None of the above. • Question 7 Given that S_n denotes the number of n-bit strings that do not contain the pattern 00, what is S_4? Answers: a. 5. b. 30. c. 8. d. None of these. • Question 8 Assume that the number of multiplication terms during the entire calculation within the line "return f(n - 1) * n" is denoted by b_n. Given the following algorithm, what is the initial condition of b_n? f(n){ if (n< 2) return 1 else return f(n - 1) * n: Answers: a. b_1 = 0. b. b_2 = 0. c. b_2 = 2. d. b_1 = 1. • Question 9 Assume that the number of multiplications in line return "f(n - 1) * n" is denoted by b_n. Given the following algorithm, what is the recurrence relation of b_n? f(n){ if (n< 2) return 1 else return f(n - 1) * n: Answers: a. b_n =b_{n - 1} + 1. b. b_n = n. c. b_n = b_{n - 1} + 2. d. b_n = n * b_{n - 1}. • Question 10 In 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. MAT2051 Discrete Mathematics Unit 8 Quiz • Question 1 Is a graph a tree? Is a tree a graph? Answers: a. Yes, Yes. b. No, Yes. c. Yes, No. d. No, No. • Question 2 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 3 Given the graph below, what type of path is path (A, D, E, C, B)? Answers: a. Simple Path. b. Cycle. c. Simple cycle. d. None of the above. • Question 4 Given the graph below, which of the following is a Hamiltonian cycle? Answers: a. (A, D, B). b. (A, D, B, C, E, D, A). c. (B, C, E, D, A, B). d. (C, E, D, A, C). • Question 5 Given the graph below, what is the total weight of the shortest weighted path from A to E: Answers: a. 8. b. 5. c. 4. d. 3. • Question 6 Given the graph below, what can we further specify this graph to be? Answers: a. A free tree. b. A rooted tree. c. Both a and b. d. None of the above. • Question 7 Given the following rooted tree (where the root is B), what node(s) is/are parent(s) of A? Answers: a. B. b. D, F. c. D, B, A. d. B, C, E. • Question 8 Which is a minimal spanning tree of the following graph? 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 9 Given the following graph, what is the preorder traversal? Answers: a. B A C D F E. b. D A F B C E. c. B A D F C E. d. D F A E C B. • Question 10 Given a tree with n vertices, what is the maximum number of edges the tree can have? Answers: a. n. b. n-1. c. n * n. d. n log n. 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.