Question 4 (3 points)

Which of the following problems have the property that they are composed of overlapping subproblems?

Select all that apply.

Question 4 options:

1)	Searching for an element in an ordered list.

2)	Sorting an array.

3)	Calculating the value of the n-th Fibonacci number.

Rod Cutting and Preliminaries

Read section 15.1 before attempting these questions.

Question 5 (1 point)

Suppose you have a rod of length n. How many different ways are there to cut this up into one or more pieces? (Assume that cuts at different places on the rod that leave you with pieces of the same size are different, as in CLRS text figure 15.2).

Question 5 options:

1)

n

2)

n2

3)

2n-1

4)

2n

5)

n!

Question 6 (1 point)

The rod-cutting problem exhibits optimal substructure - that is, the optimal solution to maximizing revenue for cutting a rod of length n incorporates the optimal solution to some subproblems of cutting a rod of length less than n. (note that this allows the possibility that the optimal solution may not involve cutting the rod at all).

Question 6 options:

	1) True
	2) False

Question 7 (1 point)

There are generally two ways of implementing dynamic programming solutions to problems, which have equal asymptotic time complexities. (The details of the problem may determine which is better in a given situation).

What are they? Select two.

Question 7 options:

1)

Bottom-up

2)	Left-to-right

3)	Right-to-left

4)

Top-down

Question 8 (1 point)

What is the worst-case asymptotic time complexity (a.k.a. "running time") of the brute-force, recursive solution to the rod cutting problem?

Question 8 options:

1)

(n)

2)

(n2)

3)

(2n)

4)

(n!)