Dynamic Programming

Question 1

(Select all that apply.) Dynamic programming is used for problems with:

A) Optimal substructure

B) Non-overlapping subproblems

C) Overlapping subproblems

Answer 1

A & B

Question 2

Without memoization, a recursive solution for Fibonacci Number would have the time complexity:

Answer 2

O(2^n)

(Each call to F(n) makes 2 addtional calls, to F(n-1) and F(n-2). Those 2 calls generate 4 calls, and so forth.

Question 3

T/F:
Usually, top-down DP algorithms are faster than bottom-up ones.

Answer 3

False

Usually, a bottom-up algorithm will be faster than the equivalent top-down algorithm as there is some overhead with recursive function calls. However, sometimes, a top-down dynamic programming approach will be the better option, such as when only a fraction of the subproblems need to be solved.

Question 4

_ approaches can be parallelized while ___ approaches cannot.

(Dynamic programming), (divide and conquer)

(Divide and conquer), (dynamic programming)

Neither can be parallelized.

Answer 4

(Divide and conquer), (dynamic programming)

Question 5

What must be done when converting a top-down dynamic programming solution into a bottom-up dynamic programming solution?

Answer 5

Find the correct order in which to iterate over the states.

(bottom-up dynamic programming solutions iterate over all of the states (starting at the base case) such that all the results necessary to solve each subproblem for the current state have already been obtained before arriving at the current state. So, to convert a top-down solution into a bottom-up solution, we must first find a logical order in which to iterate over the states.)

Question 6

[DP Recurrence Relations]
3 key characteristics of a recurrence relation

Answer 6

• A recurrence relation is an equation.
• The equation provides a general rule for the recurrence.
• The rule defines the next term as a function of the previous term(s).

Question 7

Difference in recursive calls my in DP vs Divide and Conquer

Answer 7

DC recursive calls commits to a single way of diving the input

DP considers multiple ways of defining subproblems and choosing the most optimal

Question 8

Fibonacci Subproblem

Answer 8

“Let F(i) be the i-th Fibonacci number in the sequence.”

Question 9

Fibonacci Recurrence

Answer 9

F(0) = 0, F(1) = 1
F(i) = F(i-1) + F(i-2)
where 2 <= i <= n

Question 10

[LIS]

Subproblem

Answer 10

Let L(i) be the length of LIS of A[1 … i] which includes i

Question 11

[LIS]

Recurrence

Answer 11

T(1) = 1
T(i) = max{1 + T(j) if a[i] > a[j] : where 1 <= j <= i-1}
= 1 otherwise
where 2 <= i <= n

Question 12

[LIS]
Implementation Analysis
1. Number of subproblems:
2. Runtime to fill the table:
3. How/where the final return is extracted:
4. Runtime to extract final return:

Answer 12

1. Number of subproblems: O(n)
2. Runtime to fill the table: O(n^2)
3. How/where the final return is extracted: return max{L(*)}
4. Runtime to extract final return: O(n)

Question 13

LCS Subproblem

Answer 13

Let L(i,j) be the length of longest common sequence for x[1…i] and y[1…j].

Question 14

LCS Recurrence

Answer 14

L(i,0) = 0, 0 <= i <= n
L(0,j) = 0, 0 <= j <= m

L(i,j) = 1 + L(i-1, j-1)           if x[i] = y[j]
       = max{L(i-1, j), L(i, j-1)} if x[i] != y[j]
       where 0 <= i <= n, 0 <= j <= m

Question 15

[LCS]

Implementation Analysis
1. Number of subproblems:
2. Runtime to fill the table:
3. How/where the final return is extracted:
4. Runtime to extract final return:

Answer 15

1. Number of subproblems: O(n^2)
2. Runtime to fill the table: O(n^2)
3. How/where the final return is extracted: return L(n,m)
4. Runtime to extract final return: O(1)

Question 16

Knapsack 0-1 Subproblem

Answer 16

Let K(i, b) be the max value achievable using a subset of objects x[1 … i] where total weight is less than or equal to b.

Question 17

Knapsack 0-1 Recurrence

Answer 17

K(0,b) = 0, 0 <= b <= B
K(i,0) = 0, 0 <= i <= n

K(i,b) = max{v[i] + K(i-1, b-w[i]), K(i-1, b)} if w[i] <= b
= K(i-1, b) otherwise
where 1 <= i <= n, 1 <= b <= B

Question 18

Knapsack with repeat, Subproblem

Answer 18

Let K(b) be the max value attainable with total weight <= b

Question 19

Knapsack with repeat, Recurrence

Answer 19

K(b) = 0
K(b) = max{v[i] + K(b - w[i]) : w[i] <= b}, 1 <= i <= n
where 0 <= b <= B

Question 20

[Knapsack 0-1]

Explain the greedy approach

Answer 20

1. Sort objects by value per unit of weight, v[i] / w[i]
2. Starting from highest value item, take item or skip if items doesn’t fit budget

Question 21

[Knapsack 0-1]

Explain why greedy approach fails

Answer 21

It can’t make a suboptimal choice to get a better solution in the future.

Question 22

[Knapsack]

Why is the runtime of Knapsack, O(nB), not polynomial?

Answer 22

B is simply a number, thus the number of bits required to represent number B takes space O(logB). Thus, run time is polynomial in O(n, log B).

Question 23

[CMM]

How to represent problem in binary tree

Answer 23

Root = final result
Leaf = individual matrices
Subtree = parenthetization of the problem (how solving it is structured)

Question 24

CMM Subproblem

Answer 24

Let C(i) be the minimum cost to compute A[1 … i]

Question 25

CMM Recurrence

Answer 25

Base case
C[i,j] = 0 where 1 <= j <= i <= n

C(i,j) = min{ C(i,l) + C(l+1, j) + m_{i-1} m_l m_j }
where i <= l <= j-1
and 1 <= j < i <= n

Question 26

[CMM]

Why can’t we use prefixes as subproblems?

Answer 26

If we set our recurrence on prefixes, when splitting the input into a tree, we will hit substrings where it is neither a prefix or a suffix of the original input.

Our subproblems will only have solutions for prefixes, so we can look up previous entries to solve this substring.

Question 27

[CMM]

Total cost of splitting list of matrices m[1..i] at index l

(hint: 3 components)

Answer 27

Sum of the 3 components:

Root: m[i-1], m[l], m[j]
Left: C(i,l)
Right: C(l+1, j)

Question 28

[CMM]

What do the root, left and right components of m[i-1]m[l]m[j] represent?

Answer 28

left/right subtree / subproblem
root = cost of new product

Question 29

[Contiguous Subsequence Max Sum]

Subproblem

Answer 29

Let T[i] be the max sum from substring of A[1 … i] which includes i

Question 30

[Contiguous Subsequence Max Sum]

Recurrence

Answer 30

T(0) = 0
T(i) = a[i] + max{0, a[i-1]}
where 1 <= i <= n

Question 31

[Contiguous Subsequence Max Sum]

Implementation analysis
1. Number of subproblems
2. Runtime to fill the table
3. How/where the final return is extracted from that table
4. Runtime to extract the final return

Answer 31

1. Number of subproblems: O(n)
2. Runtime to fill the table: O(n)
3. How/where the final return is extracted from that table: max{L[*]}
4. Runtime to extract the final return: O(n)

Question 32

[Edit Distance]
Input: x[1 … n], y[1 … m]

Subproblem

Answer 32

Subproblem:

Let D(i,j) be the minimum edit distance between x[1 … i] and y[1 … j] up to i and j.

Question 33

[Edit Distance]
Input: x[1…n], y[1…m]

Recurrence

Answer 33

D(i, 0) = i, 0 <= i <= n // Cost of deleting i characters
D(0, j) = j, 0 <= j <= m // Cost of inserting j characters

D(i, j) = min{
D(i-1, j-1) + diff(x[i], y[j]) # Cost to replace x[i] to y[j]
D(i-1, j) + 1 # Cost to delete x[i]
D(i, j-1) + 1 # Cost to insert y[j]
}

Question 34

[Edit Distance]

Implementation analysis
1. Number of subproblems
2. Runtime to fill the table
3. How/where the final return is extracted from that table
4. Runtime to extract the final return

Answer 34

• Number of subproblems: O(nm)
• Runtime to fill the table: O(nm)
• How/where the final return is extracted: return D(n,m)
• Runtime to extract final return: O(1)

Question 35

Algos which INCLUDE i

Answer 35

1. LIS
2. Contiguous Subsequence Max Sum
3. Chain Matrix Multiply

Question 36

When do algorithms “need” to include i

Answer 36

When your subproblem definition T[i] must include input[i].

Ex. LIS, T[i] always includes A[i]