Section 5: Advanced Dynamic Programming
CS 124 March 3, 2021
Outline
1 Dynamic Programming Review
2 Dynamic Programming on Subsets Example: Team Formation Bitmasks
3 Dynamic Programming on Trees Introduction
Example: Maximum Weighted Matching
4 Problems
Problem 1: Optimal Taxation Problem 2: Stack the Blocks Problem 3: Longest Paths in a Tree
CS 124 Advanced DP March 3, 2021 1 / 26
Dynamic Programming Review
Table of Contents
1 Dynamic Programming Review
2 Dynamic Programming on Subsets Example: Team Formation Bitmasks
3 Dynamic Programming on Trees Introduction
Example: Maximum Weighted Matching
4 Problems
Problem 1: Optimal Taxation Problem 2: Stack the Blocks Problem 3: Longest Paths in a Tree
CS 124 Advanced DP March 3, 2021 2 / 26
Dynamic Programming Review
Dynamic Programming
The central idea of dynamic programming is to break a large problem into many sub-problems, and then solve those subproblems in order to build up to a solution.
CS 124 Advanced DP March 3, 2021 3 / 26
dp[0]
dp[n]
dp[0]
dp[n]
dp[0] dp[1] dp[n – 1] dp[n]
Dynamic Programming on Subsets
Table of Contents
1 Dynamic Programming Review
2 Dynamic Programming on Subsets Example: Team Formation Bitmasks
3 Dynamic Programming on Trees Introduction
Example: Maximum Weighted Matching
4 Problems
Problem 1: Optimal Taxation Problem 2: Stack the Blocks Problem 3: Longest Paths in a Tree
CS 124 Advanced DP March 3, 2021 4 / 26
Dynamic Programming on Subsets
Example: Team Formation
Team Formation
A corporate restructuring is underway, and we’re reorganizing the company to optimize our profits. X is the set of employees.
We have a real-valued function p : 2X \ {?} ! R, which tells us the profits that can be generated by a team whose members are a subset of the employees s ✓ X .
TheprofitsfromthepartitionX=S1[S2…[Sk are p(S1)+p(S2)+…+p(Sk).
How do we maximize our profits?
CS 124 Advanced DP March 3, 2021 5 / 26
Dynamic Programming on Subsets
Example: Team Formation
Brute-Force
In order for our algorithm’s input size to be n, we let |X | = log2 n. One approach is to use brute force, and iterate over all partitions of
X.
Challenge: Prove there are nO (log log n) distinct partitions of X .
CS 124 Advanced DP March 3, 2021 6 / 26
Dynamic Programming on Subsets
Example: Team Formation
Subset Dynamic Programming
For a faster algorithm, we will use dynamic programming.
Let dp[S] be the most profit we can get from our teammates in the
subset S ✓ X. Then, we have
dp[?] = 0, dp[S] = max p(S0) + dp[S \ S0]. S0✓S
S06=?
What’s the run-time of this algorithm?
CS 124 Advanced DP March 3, 2021 7 / 26
Dynamic Programming on Subsets
Example: Team Formation
Analysis
There are n states, and each transition takes at most n time, so the run time is O(n2).
CS 124 Advanced DP March 3, 2021 8 / 26
Dynamic Programming on Subsets
Example: Team Formation
Analysis
There are n states, and each transition takes at most n time, so the run time is O(n2).
However, the analysis actually gets us a little more than that. Namely, note that there are ✓log2 n◆ sets of size i, and for each of
i
those states they take 2i iterations, so
loXg2 n ✓log2 n◆2i = (1 + 2)log2 n = nlog2(3) ⇡ n1.585,
i
i=0
which is a smaller polynomial.
CS 124 Advanced DP March 3, 2021 8 / 26
Dynamic Programming on Subsets
Example: Team Formation
Implementation Notes
a.23 : [is :
%:
In practical applications, we have to decide how to represent each
subset. Simply using the set to, say, key a map is quite ine cient. For example, in this problem we’d like iterate through each
S ✓ X,S0 ✓ S e ciently.
In order to obtain memory savings, we represent subsets with binary representations. This is a somewhat common trick which appears in many settings. One name for this trick is called “bitmasks”.
CS 124 Advanced DP March 3, 2021 9 / 26
Dynamic Programming on Subsets
Bitmasks
A story
In high school, I was part of an AI Othello tournament.
How do we represent a grid e ciently? The most standard approach is to represent the positions of the light counters with an array, say
[(3, 3), (3, 4), (4, 4), (5, 5), (6, 4), (6, 5)]
CS 124 Advanced DP March 3, 2021 10 / 26
Dynamic Programming on Subsets
Bitmasks
Using Binary
One approach is to use a bitboard, so the light counters define a number (with binary) and the dark counters also define a number.
The light counters correspond to the squares [18, 19, 27, 36, 43, 44].
The binary representation is thus
218 +219 +227 +236 +243 +244.
CS 124 Advanced DP March 3, 2021 11 / 26
Dynamic Programming on Subsets
Bitmasks
Set operations as binary operations
Another benefit of this integer representation is that certain set operations can be expressed as bitwise operations. For example, S ✓ S0 becomes
f (s, s0) := (b(s) &⇠b(s0)) = 0,
where b is the binary form of the subset s. One way to see this is to look
at this bit-by-bit.
For example, something being zero means that each bit is set to zero.
Forf(s,s0)i =1,wewouldneedb(s)i =1andb(s0)i =0forsomei – which is exactly precluded by S ✓ S0, as then i 2 S and i 62 S0.
CS 124 Advanced DP March 3, 2021 12 / 26
Dynamic Programming on Subsets
Bitmasks
An Implementation
In what follows, let x = |X |.
//set all dp[i] to negative infinity
dp[0] = 0
for (i = 0; i < 2^x; i++){
for (j = 1; j < 2^x; j++){
if (j & ~i == 0)
dp[i] = max(dp[i], dp[i - j] + p[j])
} }
return dp[2^x - 1]
CS 124 Advanced DP March 3, 2021 13 / 26
Dynamic Programming on Subsets
Bitmasks
How do we optimize this?
Note that we are blindly checking each j to see if it a subset of i, and this algorithm is still O(n2). Surely there’s a better way to do this?
//set all dp[i] to negative infinity
dp[0] = 0
for (i = 0; i < 2^x; i++){
for (j = i; j > 0; j = (j – 1) & i) dp[i] = max(dp[i], dp[i – j] + p[j])
} }
return dp[2^x – 1]
Challenge: Show that this iterates through all desired j. Can you think of
a way of replacing i j with something else, to make it faster?
CS 124 Advanced DP March 3, 2021 14 / 26
Dynamic Programming on Trees
Table of Contents
1 Dynamic Programming Review
2 Dynamic Programming on Subsets Example: Team Formation Bitmasks
3 Dynamic Programming on Trees Introduction
Example: Maximum Weighted Matching
4 Problems
Problem 1: Optimal Taxation Problem 2: Stack the Blocks Problem 3: Longest Paths in a Tree
CS 124 Advanced DP March 3, 2021 15 / 26
Dynamic Programming on Trees
Introduction
Tree-based dynamic programming
yin a. .
Many problems are particularly natural on trees. Dynamic Programming is often a very useful technique on these problems, where the subproblems are given over the subtrees.
Each of the subproblems is solving the problem over a given subtree.
At each step, we solve the problem over each “direct” subtree, and then aggregate those results into a solution for this subtree.
CS 124 Advanced DP March 3, 2021 16 / 26
Dynamic Programming on Trees
Introduction
Pseudocode, first attempt
dfs(v){
for (vertex j: N(v)){
dfs(j);
//calculate dp[v] with dp[j]
} }
dfs(root)
What’s the problem with this algorithm?
CS 124 Advanced DP March 3, 2021 17 / 26
Dynamic Programming on Trees
Introduction
Pseudocode, fixed
dfs(v, p){
for (vertex j: N(v)){
if (j != p) dfs(j, v); //calculate dp[v] with dp[j]
} }
dfs(root, nil)
CS 124 Advanced DP March 3, 2021 18 / 26
Dynamic Programming on Trees
Example: Maximum Weighted Matching
Maximum Weighted Matching
We have a tree. What’s the highest-weight matching in this tree? A matching is a set of edges with no vertex overlap.
‘nnotatm!!!in ,
Figure: A tree.
CS 124 Advanced DP March 3, 2021 19 / 26
l✓ y l
CS 124
Advanced DP
March 3, 2021 20 / 26
Dynamic Programming on Trees Example: Maximum Weighted Matching
Algorithm
To solve this problem, we write dp[v][0] to be the largest matching without using the root, and dp[v][1] to be the largest matching using the root.
dplvt.CO]= Imax(dpc’s]Col, dplj]CD)
m IENG)
je p
dplvlll =
Yeah
•
]
;
*p
)
,(Wv. t dpcilco]
smaxcddr.pk?Yfjy
KENN) Ktp’s
Dynamic Programming on Trees
Example: Maximum Weighted Matching
Algorithm
To solve this problem, we write dp[v][0] to be the largest matching without using the root, and dp[v][1] to be the largest matching using the root.
Then, we have that
dp[v][1]= max 0B@wu,v +dp[u][0]+ X max(dp[j][0],dp[j][1])1CA
and
u2N(v) j2N(v) u6=p j6=u,p
X
dp[v][0] = max(dp[j][0],dp[j][1]). j2N(v)
j 6=p
and the answer is max(dp[r][0],dp[r][1]).
CS 124 Advanced DP March 3, 2021 20 / 26
Dynamic Programming on Trees
Example: Maximum Weighted Matching
Runtime Analysis
What’s the runtime of this algorithm?
n times
O(n’ )
operatic” //calculate dp[v] with dp[j]
dfs(v, p){
o ( n )
for (vertex j: N(v)){ m m m
if (j != p) dfs(j, v); }
}
dfs(root, nil)
CS 124 Advanced DP March 3, 2021 21 / 26
Dynamic Programming on Trees
Example: Maximum Weighted Matching
Runtime Analysis
What’s the runtime of this algorithm?
d
O (d)
O ( d’ )
dfs(v, p){
mm
o (n ) //calculate dp[v] with dp[j]
for (vertex j: N(v)){ if (j != p) dfs(j, v);
w
} }
dfs(root, nil)
Since each vertex j which is not the root has dfs called on it exactly once, the total amount of calls across all internal loops is is O(n). However, we need to make sure that the internal processing is also O(d) where d is the number of neighbors, or we might be in trouble!
rumrunner
CS 124 Advanced DP March 3, 2021 21 / 26
Worked Example
CS 124
[0,03 Advanced DP
22 / 26
[0,6]
18
[X0,9 ) [ 0,0]
[0,0]
.
[0,0] March 3, 2021
Dynamic Programming on Trees
C
Example: Maximum Weighted Matching
*
100
[0,03
100
X
[
Is , /
4.bywith root without root
Problems
Table of Contents
1 Dynamic Programming Review
2 Dynamic Programming on Subsets Example: Team Formation Bitmasks
3 Dynamic Programming on Trees Introduction
Example: Maximum Weighted Matching
4 Problems
Problem 1: Optimal Taxation Problem 2: Stack the Blocks Problem 3: Longest Paths in a Tree
CS 124 Advanced DP March 3, 2021 23 / 26
Problems
Problem 1: Optimal Taxation
Problem 1: Optimal Taxation
You are the king of a kingdom that’s set up like a tree, and you want to collect some taxes. You know that each city has a “tax potential” ti that you can collect. However, you don’t want to tax adjacent cities, because they might talk to each other and begin a revolt. Find the maximum tax you can collect in linear time.
÷:*.
CS 124 Advanced DP March 3, 2021 24 / 26
Problems
Problem 2: Stack the Blocks
Problem 2: Stack the Blocks
power – 9-3-5=1 D
We have n blocks, each with weight wi and strength bi . We stack the blocks on top of each other in some order.
The power of a block is its strength minus the sum of the weights which lie on it.
The strength factor of a stack is the minimum power of any particular block.
Give a O(n · 2n) algorithm to find the maximum possible strength factor across all permutations containing all of the blocks (note: answer might be negative).
57 Sg
CS 124 Advanced DP March 3, 2021 25 / 26
Problems
Problem 3: Longest Paths in a Tree
Problem 3: Longest Path in a Tree
Find the length of the longest path in a tree, where the edges are weighted.
CS 124 Advanced DP March 3, 2021 26 / 26