Order the following four steps in the application of dynamic programming from first to last

Question 1 options:

Question 1 (2 points)

Order the following four steps in the application of dynamic programming from first to last

Question 1 options:

1234	Recursively define the value of an optimal solution.
1234	Compute the value of an optimal solution.
1234	Characterize the structure of an optimal solution.
1234	Construct the details of the optimal solution with a given value from computed information.

Question 2 (2 points)

In order for dynamic programming to apply to a problem, which of the following properties must that problem have?

Select all that apply.

Question 2 options:

1)	The problem must have disjoint subproblems.

2)	The problem must have overlapping subproblems.

3)	The non-dynamic-programming solution to the problem must take exponential time.

4)	The problem must have optimal substructure.

Question 3 (3 points)

Which of the following problems exhibit optimal substructure? (That is, an optimal solution to a problem will contain an optimal solution to subproblems.)

Select all that apply.

Question 3 options:

1)	The shortest path problem: Finding the shortest path from point A to point B in a graph.

2)	The problem of packing a box full of material to maximize the total value of material in the box.

3)	The longest path problem: Finding the longest path (without any cycles) from point A to point B in a graph.

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!)

Question 9 (1 point)

What is the worst-case asymptotic time complexity (a.k.a. "running time") of the dynamic programming solution to the rod cutting problem?

Question 9 options:

1)

(n)

2)

(n2)

3)

(2n)

4)

(n!)