Lesson test: Dynamic programming

1.[3p]
What does "overlapping subproblems" mean?

The recursion visits a small set of distinct subproblems an enormous number of times

Correct

The subproblems share some of their input elements

The answer is: The recursion visits a small set of distinct subproblems an enormous number of times

The subproblems can be solved in any order

The answer is: The recursion visits a small set of distinct subproblems an enormous number of times

Each subproblem is half the size of its parent

The answer is: The recursion visits a small set of distinct subproblems an enormous number of times

2.[2p]
Mergesort would be faster if its subproblems were memoised.

True

The answer is: False

False

Correct

3.[3p]
Pieces of length 1 to 8 sell for 2, 5, 7, 8, 10, 17, 17 and 20. What is the best revenue from a rod of length 8?

CorrectNot quite: 22

5.[3p]
A bag holds 8 kg and the items are (3 kg, 4), (4 kg, 5), (2 kg, 3) and (5 kg, 6). What is the best value?

CorrectNot quite: 10

6.[2p]
How many cells does the knapsack table have for 40 items and a capacity of 500, counting the zero row and column?

CorrectNot quite: 20541

8.[3p]
Which of these are true of dynamic programming?

Select all that apply

It needs both overlapping subproblems and optimal substructure

Correct

The running time is the number of table cells times the work per cell

Correct

Memoisation computes only the subproblems actually reached

Correct

Tabulation always uses less total memory than memoisation

The answer is: It needs both overlapping subproblems and optimal substructure, The running time is the number of table cells times the work per cell, Memoisation computes only the subproblems actually reached

9.[3p]
Why is the $Θ (n W)$ knapsack algorithm called pseudo-polynomial?

$W$ is written in $\log_{2} W$ bits, so the table is exponential in the length of the input

Correct

It is polynomial only on average

The answer is: $W$ is written in $\log_2 W$ bits, so the table is exponential in the length of the input

It uses a table rather than recursion

The answer is: $W$ is written in $\log_2 W$ bits, so the table is exponential in the length of the input

The constant hidden by $Θ$ is very large

The answer is: $W$ is written in $\log_2 W$ bits, so the table is exponential in the length of the input

Sign in

Dynamic programming

1.[3p]
What does "overlapping subproblems" mean?

2.[2p]
Mergesort would be faster if its subproblems were memoised.

3.[3p]
Pieces of length 1 to 8 sell for 2, 5, 7, 8, 10, 17, 17 and 20. What is the best revenue from a rod of length 8?

4.[2p]
With those same prices, what is the best revenue from a rod of length 5?

5.[3p]
A bag holds 8 kg and the items are (3 kg, 4), (4 kg, 5), (2 kg, 3) and (5 kg, 6). What is the best value?

6.[2p]
How many cells does the knapsack table have for 40 items and a capacity of 500, counting the zero row and column?

7.[3p]
What is the edit distance between "kitten" and "sitting"?

8.[3p]
Which of these are true of dynamic programming?

9.[3p]
Why is the $Θ (n W)$ knapsack algorithm called pseudo-polynomial?

1.[3p] What does "overlapping subproblems" mean?

2.[2p] Mergesort would be faster if its subproblems were memoised.

3.[3p] Pieces of length 1 to 8 sell for 2, 5, 7, 8, 10, 17, 17 and 20. What is the best revenue from a rod of length 8?

4.[2p] With those same prices, what is the best revenue from a rod of length 5?

5.[3p] A bag holds 8 kg and the items are (3 kg, 4), (4 kg, 5), (2 kg, 3) and (5 kg, 6). What is the best value?

6.[2p] How many cells does the knapsack table have for 40 items and a capacity of 500, counting the zero row and column?

7.[3p] What is the edit distance between "kitten" and "sitting"?

8.[3p] Which of these are true of dynamic programming?

9.[3p] Why is the Θ(nW) knapsack algorithm called pseudo-polynomial?

1.[3p]
What does "overlapping subproblems" mean?

2.[2p]
Mergesort would be faster if its subproblems were memoised.

3.[3p]
Pieces of length 1 to 8 sell for 2, 5, 7, 8, 10, 17, 17 and 20. What is the best revenue from a rod of length 8?

4.[2p]
With those same prices, what is the best revenue from a rod of length 5?

5.[3p]
A bag holds 8 kg and the items are (3 kg, 4), (4 kg, 5), (2 kg, 3) and (5 kg, 6). What is the best value?

6.[2p]
How many cells does the knapsack table have for 40 items and a capacity of 500, counting the zero row and column?

7.[3p]
What is the edit distance between "kitten" and "sitting"?

8.[3p]
Which of these are true of dynamic programming?

9.[3p]
Why is the $Θ (n W)$ knapsack algorithm called pseudo-polynomial?