CSE 101
Algorithm Design & Analysis
Lecture 6
Today’s plan
Dynamic programming:
- Knapsack (with and without repetition)
- Independent sets in trees - if time
- String interleaving (homework 1) - if time
Knapsack
Suppose that you have a bag that can store up to 15lbs. You go into a store
that has the following 4 kinds of items, each with a weight and a value:
- Item 1: weight 9lbs, value $45
- Item 2: weight 5lbs, value $30
- Item 3: weight 6lbs, value $32
- Item 4: weight 3lbs, value $15
Assume that you’re allowed to take any number of each items, as long as they
all fit in your bag. How would you pick the items to maximize the total value?
How about if you’re only allowed to take at most one of each item?
Knapsack
A burglar has broken into a store. The store items 1…n, where item i has
weight wi and value vi. The burglar has a knapsack with capacity C. The burglar
can take as many items as they want, as long as the weight of all items doesn’t
exceed the knapsack capacity C. Which items should the burglar take to
maximize the total value, assuming:
- Each type of item has unlimited copies? (with repetition)
- Each type of item only has one copy? (without repetition)
Knapsack with repetition
Question: At each step, which type of item does the burglar take? Assume
capacity 15lbs.
- Item 1: weight 9lbs, value $45
- Item 2: weight 5lbs, value $30
- Item 3: weight 6lbs, value $32
- Item 4: weight 3lbs, value $15
Knapsack with repetition
C
{1,2,...,n}
C - w1
{1,2,...,n}
C - w2
{1,2,...,n}
C - wn
{1,2,...,n}
…
C - w1 - w1
{1,2,...,n}
C - w1 - w2
{1,2,...,n}
C - w2 - w1
{1,2,...,n}
…
C - w2 - w2
{1,2,...,n}
C - wn - wn
{1,2,...,n}
…
… … … … …
Knapsack with repetition
C
{1,2,...,n}
C - w1
{1,2,...,n}
C - w2
{1,2,...,n}
C - wn
{1,2,...,n}
…
C - w1 - w1
{1,2,...,n}
C - w1 - w2
{1,2,...,n}
C - w2 - w1
{1,2,...,n}
…
C - w2 - w2
{1,2,...,n}
C - wn - wn
{1,2,...,n}
…
… … … … …
Same subproblem!
Knapsack with repetition
C
{1,2,...,n}
C - w1
{1,2,...,n}
C - w2
{1,2,...,n}
C - wn
{1,2,...,n}
…
C - w1 - w1
{1,2,...,n}
C - w1 - w2
{1,2,...,n}
C - w2 - w1
{1,2,...,n}
…
C - w2 - w2
{1,2,...,n}
C - wn - wn
{1,2,...,n}
…
… … … … …
What is changing between each recursive call?
Knapsack with repetition
C
{1,2,...,n}
C - w1
{1,2,...,n}
C - w2
{1,2,...,n}
C - wn
{1,2,...,n}
…
C - w1 - w1
{1,2,...,n}
C - w1 - w2
{1,2,...,n}
C - w2 - w1
{1,2,...,n}
…
C - w2 - w2
{1,2,...,n}
C - wn - wn
{1,2,...,n}
…
… … … … …
Each recursive call, we want the max value by taking from items 1…n for some
changing max capacity. This is a rephrasing of the original problem!
Knapsack with repetition
1. Subproblems
Let K[i] be the max value we can get from items 1…n (with repetition) with a
knapsack of capacity i.
Knapsack with repetition
2. Base case(s)
Which subproblem(s) can we solve independently (without needing results
from other subproblems)?
Knapsack with repetition
2. Base case(s)
K[0] = 0. If the knapsack has capacity 0, we can’t put anything in it.
Knapsack with repetition
3. Recurrence relation
How do we solve K[i] for any general value of i?
i
{1,2,...,n}
i - w1
{1,2,...,n}
i - w2
{1,2,...,n}
i - wn
{1,2,...,n}
…
i - w3
{1,2,...,n}
Knapsack with repetition
3. Recurrence relation
Which item do we take?
- Case 0: If we don’t take any item, K[i] = 0
- Case 1: If we take item 1, K[i] = v1 + K[i - w1] (if w1 ≤ i)
- Case 2: If we take item 2, K[i] = v2 + K[i - w2] (if w2 ≤ i)
- …
- Case n: If we take item n, K[i] = vn + K[i - wn] (if wn ≤ i)
Which case do we take?
Knapsack with repetition
3. Recurrence relation
We take the case with the largest resulting value. So to summarize:
K[i] = max1 ≤ j ≤ n, w_j ≤ i (vj + K[i - wj])
Knapsack with repetition
4. Ordering the subproblems
Which subproblem(s) does each K[i] depend on?
K[0] K[1] K[2] K[3] K[4] … K[i-1] K[i] … K[C]
Knapsack with repetition
4. Ordering the subproblems
Each K[i] depends on all K[0]...K[i-1]. So we should solve the subproblems for
increasing values of i (left to right in the array K).
K[0] K[1] K[2] K[3] K[4] … K[i-1] K[i] … K[C]
Knapsack with repetition
5. Final output
Which subproblem(s) correspond with the answer we want?
Knapsack with repetition
5. Final output
K[C], “the max value we can get from items 1…n (with repetition) with a
knapsack of capacity C.”
Knapsack with repetition
6. Pseudocode
KnapsackWithRepetition(C, w[1…n], v[1…n]):
Declare K[0…C]. Let K[0] = 0
For i = 1…C:
K[i] = 0
For j = 1…n:
If w[j] ≤ i, K[i] = max(K[i], v[j] + K[i - w[j])
Return K[C]
Knapsack with repetition
7. Runtime
Runtime of DP: (number of subproblems)(time per subproblem) + overhead
- Number of subproblems:
- Time per subproblem:
- Overhead:
Knapsack with repetition
7. Runtime
Runtime of DP:
- Number of subproblems: O(C) for all K[i], 0 ≤ i ≤ C
- Time per subproblem: O(n) to check all n items
- Overhead: O(C) to declare array, O(1) to return
Overall: O(nC)
Knapsack without repetition
Recall the question for the case with repetition: At each step, which type of
item does the burglar take? Assume capacity 15lbs.
- Item 1: weight 9lbs, value $45
- Item 2: weight 5lbs, value $30
- Item 3: weight 6lbs, value $32
- Item 4: weight 3lbs, value $15
Will this approach still be efficient when there is no repetition?
Knapsack without repetition
C
{1,2,...,n}
C - w1
{2,...,n}
C - w2
{1,3,...,n}
C - wn
{1,2,...,n-1}
…
C - w1 - w2
{3,...,n}
C - w1 - w3
{2,4,...,n}
C - w2 - w1
{3,...,n}
…
C - w2 - w3
{1,4,...,n}
C - wn - wn-1
{1,2,...,n-2}
…
… … … … …
Knapsack without repetition
C
{1,2,...,n}
C - w1
{2,...,n}
C - w2
{1,3,...,n}
C - wn
{1,2,...,n-1}
…
C - w1 - w2
{3,...,n}
C - w1 - w3
{2,4,...,n}
C - w2 - w1
{3,...,n}
…
C - w2 - w3
{1,4,...,n}
C - wn - wn-1
{1,2,...,n-2}
…
… … … … …
We note that while capacities can range from 0…C, the set of items available
can be any subset of {1…n}, and there is an exponential number of subsets.
Knapsack without repetition
We see that the approach of asking which item to take will result in an
exponential number of subproblems.
However, we note the following:
- If we take item n, then we have value vn, and we now consider items 1…n-
1 and capacity C - wn
- If we don’t take item n, then we consider items 1…n-1 and capacity C
Knapsack without repetition
In both cases, we want the max value from items 1…n-1 and some max
capacity. This is a rephrasing of the original problem!
So now, we change the question to ask: At each step, does the burglar take
the last item?
Knapsack without repetition
C
{1,2,...,n}
C - wn
{1,2,...,n-1}
C
{1,2,...,n-1}
C - wn - wn-1
{1,2,...,n-2}
C - wn
{1,2,...,n-2}
C - wn-1
{1,2,...,n-2}
C
{1,2,...,n-2}
… … … …
Knapsack without repetition
C
{1,2,...,n}
C - wn
{1,2,...,n-1}
C
{1,2,...,n-1}
C - wn - wn-1
{1,2,...,n-2}
C - wn
{1,2,...,n-2}
C - wn-1
{1,2,...,n-2}
C
{1,2,...,n-2}
… … … …
Same subproblem if
wn = wn-1!
Knapsack without repetition
C
{1,2,...,n}
C - wn
{1,2,...,n-1}
C
{1,2,...,n-1}
C - wn - wn-1
{1,2,...,n-2}
C - wn
{1,2,...,n-2}
C - wn-1
{1,2,...,n-2}
C
{1,2,...,n-2}
… … … …
We note that now, every recursive calls have the form “max value for items
1…i (without repetition) and some changing max capacity.” We’ve improved
the number of different subsets considered from exponential to linear!
Knapsack without repetition
1. Subproblems
Let K[i, j] be the max value we can get from items 1…i (without repetition) with
a knapsack of capacity j.
Knapsack without repetition
2. Base case(s)
Which subproblem(s) can we solve independently (without needing results
from other subproblems)?
Knapsack without repetition
2. Base case(s)
K[i, 0] = 0 for all 0 ≤ i ≤ n. If the knapsack has capacity 0, we can’t put anything
in it.
K[0, j] = 0 for all 0 ≤ j ≤ C. If there are no items, we can’t take anything
regardless of knapsack size.
Knapsack without repetition
3. Recurrence relation
How do we solve K[i, j] for any general value of i, j?
j
{1,2,...,i}
j - wi
{1,2,...,i-1}
j
{1,2,...,i-1}
Knapsack without repetition
3. Recurrence relation
Which item do we take?
- Case 1: If we don’t take item i, K[i, j] = K[i-1, j]
- Case 2: If we take item i, K[i, j] = vi + K[i-1, j - wi] (if wi ≤ j)
Which case do we take?
Knapsack without repetition
3. Recurrence relation
We take the case with the largest resulting value. So to summarize:
If wi > j, K[i, j] = K[i-1, j]
Else, K[i, j] = max(K[i-1, j], vi + K[i-1, j - wi]
Knapsack without repetition
4. Ordering the subproblems
Which subproblem(s) does each K[i, j] depend on?
… … … … … … … … … …
K[i-1, 0] K[i-1, 1] K[i-1, 2] K[i-1, 3] K[i-1, 4] … K[i-1,j-1] K[i-1, j] … K[i-1, C]
K[i, 0] K[i, 1] K[i, 2] K[i, 3] K[i, 4] … K[i, j-1] K[i, j] … K[i, C]
… … … … … … … … … …
Knapsack without repetition
4. Ordering the subproblems
Each K[i, j] depends on 2 cells on the row before it. So we should solve the
subproblems in order of each row from top to bottom (for each row we can
solve left to right).
… … … … … … … … … …
K[i-1, 0] K[i-1, 1] K[i-1, 2] K[i-1, 3] K[i-1, 4] … K[i-1,j-1] K[i-1, j] … K[i-1, C]
K[i, 0] K[i, 1] K[i, 2] K[i, 3] K[i, 4] … K[i, j-1] K[i, j] … K[i, C]
… … … … … … … … … …
Knapsack without repetition
5. Final output
Which subproblem(s) correspond with the answer we want?
Knapsack without repetition
5. Final output
K[n, C], “the max value we can get from items 1…n (without repetition) with a
knapsack of capacity C.”
Knapsack without repetition
6. Pseudocode
KnapsackWithoutRepetition(C, w[1…n], v[1…n]):
Declare K[0,...n, 0…C].
Let K[0, j] = K[i, 0] = 0 for all 0 ≤ i ≤ n, 0 ≤ j ≤ C.
For i = 1…n:
For j = 1…C:
If w[i] > j, K[i, j] = K[i-1, j]
Else, K[i, j] = max(K[i-1, j], v[i] + K[i-1, j - w[i])
Return K[n, C]
Knapsack without repetition
7. Runtime
Runtime of DP: (number of subproblems)(time per subproblem) + overhead
- Number of subproblems:
- Time per subproblem:
- Overhead:
Knapsack without repetition
7. Runtime
Runtime of DP:
- Number of subproblems: O(nC) for all K[i, j], 0 ≤ i ≤ n, 0 ≤ j ≤ C.
- Time per subproblem: O(1) to check 2 cells in the table K
- Overhead: O(nC) to declare array, O(1) to return
Overall: O(nC)
Knapsack runtime
We observed that the runtime of both versions of knapsack is O(nC). This is in
fact not polynomial time!
When we consider linearly increasing size of the input, for the number of
items, that would go from n, n+1, n+2,... For the capacity, the size is actually
the number of bits of C, which is x = log(C), x+1, x+2,...
Since knapsack’s runtime grows in terms of the value of C and not the size of
C, it is not polynomial time. Knapsack’s runtime is in a class known as pseudo-
polynomial, and the knapsack problem is actually NP-complete.
Max independent set
Given a graph G(V, E), an independent set is a subset S ⊆ V such that for all
edges (u, v) ⊆ E, u ∉ S or v ∉ S. We want to find the largest independent set.
A
B
C
D E
F
Max independent set
Determining the largest independent set of any graph also turns out to be NP-
complete.
However, if the graph is a tree, we can take advantage of the structure of trees
to improve the runtime.
How? With dynamic programming!
Max independent set of a tree
We want to find the max independent set of the
tree rooted at A.
What decision can we try making to know which
vertices will be in the independent set?
A
B C D
E F G
H
Max independent set of a tree
If A is in the independent set S, then what is the
size of the max independent set?
If A is not in S, then what is the size of the
max independent set?
A
B C D
E F G
H
Max independent set of a tree
We see that in both cases, we need to find the max
independent set of various subtrees of the tree
rooted at A.
A
B C D
E F G
H
Max independent set of a tree
1. Subproblems
Let I[u] be the max independent set of the tree rooted at vertex u
Max independent set of a tree
2. Base case(s)
Max independent set of a tree
2. Base case(s)
I[u] = 1 if u is a leaf
Max independent set of a tree
3. Recurrence relation
Recall the 2 cases we discussed
A
B C D
E F G
Max independent set of a tree
3. Recurrence relation
Case 1: u is in the max independent set. I[u] = 1 + ∑ w grandchildren of u I[w]
Case 2: u is not in the max independent set. I[u] = ∑ x children of u I[x]
We take the max of the 2 cases. Therefore:
I[u] = max(1 + ∑ w grandchildren of u I[w], ∑ x children of u I[x])
Max independent set of a tree
4. Ordering the subproblems
Which subproblem(s) does each I[u] depend on?
Max independent set of a tree
4. Ordering the subproblems
Each I[u] depends on I[v], where v is either u’s children or grandchildren. So
we should solve the subproblems in order of each tree level from bottom to
top.
Max independent set of a tree
5. Final output
Which subproblem(s) correspond with the answer we want?
Max independent set of a tree
5. Final output
I[v], “the max independent set of the tree rooted at vertex v.”
Max independent set of a tree
6. Pseudocode
MaxIndependentSet(G(V, E), root v): (assume V ordered in levels bottom up)
Declare K[m] for all m ∈ V
For each u ∈ V:
If u is a leaf: I[u] = 1
Else, I[u] = max(1 + ∑ w grandchildren of u I[w], ∑ x children of u I[x])
Return I[v]
Max independent set of a tree
7. Runtime
Runtime of DP:
- Number of subproblems: |V|
- Time per subproblem: |children of u| + |grandchildren of u|
- Overhead: O(|V|) to declare array
Overall: O(|V|)
Interleaving string
Given 3 strings x (length n), y (length m), and z (length n+m), determine if z is
an interleaving of x and y.
Backtracking algorithm:
BTInterleaving(x1…xn, y1...ym, z1...zn+m):
If n = 0, return TRUE if y1...ym = z1...zm, else return FALSE
If m = 0, return TRUE if x1...xn = z1...zn, else return FALSE
If x1 = z1 and BTInterleaving(x2…xn, y1...ym, z2...zn+m), return TRUE
If y1 = z1 and BTInterleaving(x1…xn, y2...ym, z2...zn+m), return TRUE
Return FALSE
Interleaving string
a) Draw the recursion tree for x = 1010, y = 0011, z = 10001101
x = 1010
y = 0011
z = 10001101
x = 010
y = 0011
z = 0001101
x = 10
y = 0011
z = 001101
x = 010
y = 011
z = 001101
x = 10
y = 011
z = 01101
x = 10
y = 11
z = 1101
x = 0
y = 11
z = 101
x = 0
y = 1
z = 01
x =
y = 1
z = 1
x = 10
y = 1
z = 101
x = 0
y = 1
z = 01
x =
y = 1
z = 1
x = 10
y =
z = 01
x = 10
y = 011
z = 01101
x = 010
y = 11
z = 01101
x = 10
y = 11
z = 1101
x = 10
y = 11
z = 1101
…
…
Interleaving string
b) What is an upper bound on the total number of recursive calls this
algorithm might make? (in terms of n and m)
If x1 = y1 = z1, then the function makes both recursive calls. If this happens
every time, then we’ll always make 2 recursive calls. We might only use 1 digit
from z each time, so the recursion tree has n+m levels, and each level doubles
the number of recursive calls from the last in the worst case.
Overall an upper bound for the number of recursive calls is 2n+m
Interleaving string
c) What are the subproblems?
We see that between each recursive calls, the first character of x and y may
change. We define IS[i, j] = if xi…xn and yj…ym is an interleaving of zn+m-i-j+2…zn+m.
Alternatively you can use the last character of x and y. We define IS[i, j] = if
x1…xi and y1…yj is an interleaving of z1…zi+j. We’ll use this convention to
simplify notation, though we note that simple modifications can make the
other convention work as well.
Interleaving string
c) What is the algorithm?
Base case(s):
- IS[0, 0] = TRUE (this is when both x and y are empty)
- IS[0, j] = TRUE if y1…yj = z1…zj, else IS[0, j] = FALSE (for all 1 ≤ j ≤ m)
- IS[i, 0] = TRUE if x1…xi = z1…zi, else IS[i, 0] = FALSE (for all 1 ≤ i ≤ n)
Recurrence relation:
- IS[i, j] = TRUE if (xi = zi+j and IS[i-1, j]) or (yj = zi+j and IS[i, j-1]). Else IS[i, j] =
FALSE
Interleaving string
Ordering of subproblems:
- We note that IS[i, j] depends on IS[i-1, j] and IS[i, j-1], so we solve the
problems by rows top to bottom, and in each row we solve left to right
(for i=1…n; for j=1…m)
Final output:
- IS[n, m]
… … … …
… IS[i-1, j-1] IS[i-1, j] …
… IS[i, j-1] IS[i, j] …
… … … …
Interleaving string
Pseudocode (THIS IS THE ONLY PART YOU NEED FOR THE HOMEWORK):
StringInterleaving(x[1…n], y[1…m], z[1…n+m]):
Declare IS[0…n, 0…m]. Let IS[0, 0] = TRUE
For i = 1…n: If x1…xi = z1…zi then IS[i, 0] = TRUE. Else IS[i, 0] = FALSE
For j = 1…m: If y1…yj = z1…zj then IS[0, j] = TRUE. Else IS[0, j] = FALSE
For i = 1…n:
For j = 1…m:
If (xi = zi+j and IS[i-1, j]) or (yj = zi+j and IS[i, j-1]) then
IS[i, j] = TRUE
Else IS[i, j] = FALSE
Return IS[n, m]
Interleaving string
e) What is the runtime?
- Number of subproblems: O(nm)
- Time per subproblem: O(1)
- Overhead: O(nm) to create array, O(1) to return
Overall: O(nm)
Any questions?
Thank you!

欢迎咨询51作业君