Capella MAT2051 2019 October Unit 6 Quiz Latest

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.

-
Rating:
5/
Solution: Capella MAT2051 2019 October Unit 6 Quiz Latest