Discrete Math

Current Location

Take Test: [u06q1] Unit 6 Quiz 1

SKIP TO COURSE MENUSKIP TO TOP FRAME TABS

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}:

Answer

	a.	1.
	b.	2.
	c.	3.
	d.	4.

10 points

Question 2

1.

Which of the following is O(n)?

Answer

	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?

Answer

	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:

Answer

	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?

Answer

	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?

Answer

	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?

Answer

	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:

Answer

	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:

Answer

	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:

Answer

	a.	O(n).
	b.	O(log(n)).
	c.	O(n!).
	d.	None of the above.

10 points

Bottom of Form