# Discrete Math- Unit 6 Quiz 1.

Content

Top of Form
Assistive Technology Tips [opens in new window]

Instructions

Description
View Quiz Description
Instructions

Multiple Attempts
Not allowed. This Test can only be taken once.
Force Completion
This Test can be saved and resumed later.
Question Completion Status:

Question 1

1.

How many times does the computer print the string "Hello"?
i = 2
while (i < 4) {

print ("Hello")

i = i + 1}:

a.
1.

b.
2.

c.
3.

d.
4.
10 points

Question 2

1.

Which of the following is O(n)?

a.
3n + 1.

b.
n * log(n).

c.
n * n + n.

d.
None of the above.
10 points

Question 3

1.

If each of the following describes the run time of an algorithm, which of the following could have the longest run time?

a.
O(nlog(n)).

b.
O(n!).

c.
O(n/2).

d.
O(n * n).
10 points

Question 4

1.

What does the following algorithm return?
f(n){
if (n< 2)

return 1

else

return f(n - 1) * n:

a.
n!

b.
The maximum divisor of n.

c.
(n - 1)!

d.
n 2.
10 points

Question 5

1.

Given that S_n denotes the number of n-bit strings that do not contain the pattern 00, what are the initial conditions?

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.
10 points

Question 6

1.

Given that S_n denotes the number of n-bit strings that do not contain the pattern 00, what is the recurrence relation?

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.
10 points

Question 7

1.

Given that S_n denotes the number of n-bit strings that do not contain the pattern 00, what is S_4?

a.
5.

b.
30.

c.
8.

d.
None of these.
10 points

Question 8

1.

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 ofb_n?
f(n){
if (n< 2)

return 1

else

return f(n - 1) * n:

a.
b_1 = 0.

b.
b_2 = 0.

c.
b_2 = 2.

d.
b_1 = 1.
10 points

Question 9

1.

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:

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}.
10 points

Question 10

1.

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: