Algorithms & Data Structures (Winter 2022) Algorithm Paradigms – Dynamic Programming 2
Announcements
• A2 is out (just after this lecture).
Copyright By PowCoder代写 加微信 powcoder
• Please start working on it early. • Good for you.
• Good for us.
• A2 is a good preparation for the midterm.
• You have 3 weeks; however this assignment is harder than A1.
• Plus the reading week is in the middle.
• Midterm will be held two days after the due date. • No extensions.
• Complete Search
• Divide and Conquer.
• Dynamic Programming. • Introduction.
• Examples.
Dynamic Programming– Take home picture
Dynamic Programming– 2D – Knapsack
Taken form baeldung.com
Dynamic Programming– 2D – Knapsack
Step 1: Identify the sub-problems (in words). Step 1.1: Identify the possible sub-problems.
Let OPT(i) be the maximum total value of items 1 to i (i.e., value of the optimal solution to the problem including activities 1 to i).
I just copy the same definition used for the weighted interval scheduling
ì LetOPT(i)bethemaximumtotalweightofcompatibleactivities1toi(i.e., value of the optimal solution to the problem including activities 1 to i).
Dynamic Programming– 2D – Knapsack
Step 2: Find the recurrence.
Step 2.1: What decision do I make at every step?.
Case 1: OPT does not select (activity) item i
• Must include optimal solution on other (activities) items {1, 2, …, i-1}.
Case 2: OPT selects (activity) item i
• (activity) Add weight wi — (item) Add weight wi and value vi
• (activity) Cannot use incompatible activities – (item) ??
• (activity) Must include optimal solution on remaining compatible activities {1, 2,
…,p(j)}. –(item)??
• Selecting item i does not immediately imply that we will have to reject
other items
• Without knowing what other items were selected before i, we do not even
know if we have enough room for i.
Dynamic Programming– 2D – Knapsack
Step 2: Find the recurrence.
Case 2: OPT selects (activity) item i
• Selecting item i does not immediately imply that we will have to reject
other items
• Without knowing what other items were selected before i, we do not even
know if we have enough room for i.
Conclusion: We need more subproblems!!!!!
After item n is included in the solution, a weight of wn is 8 used up and there is W – wn available weight left
Dynamic Programming– 2D – Knapsack
Step 1: Identify the sub-problems (in words). Step 1.1: Identify the possible sub-problems.
Let OPT(i, w) be the maximum profit subset of items 1 to i with weight limit w.
Dynamic Programming– 2D – Knapsack
Step 2: Find the recurrence. Case 1: OPT does not select item i
• OPT selects best of {1, 2, …, i-1} using weight limit w.
Case 2: OPT selects item i
• New weight limit = w – wi
• OPT selects best of {1, 2, … , i-1 } using this new weight limit.
Optimal substructure property
Dynamic Programming– 2D – Knapsack
Dynamic Programming– 2D – Knapsack
Max weight W = 11
Dynamic Programming– 2D – Knapsack
{1,2,3,4,5}
Dynamic Programming– 2D – Knapsack
{1,2,3,4,5}
Dynamic Programming– 2D – Knapsack
{1,2,3,4,5}
Dynamic Programming– 2D – Knapsack
{1,2,3,4,5}
V2+M(i-1,w-w2)
Dynamic Programming– 2D – Knapsack
{1,2,3,4,5}
Dynamic Programming– 2D – Knapsack
{1,2,3,4,5}
Dynamic Programming– 2D – Knapsack
{1,2,3,4,5}
Dynamic Programming– 2D – Knapsack
{1,2,3,4,5}
Dynamic Programming– 2D – Knapsack
{1,2,3,4,5}
Dynamic Programming– 2D – Knapsack
Dynamic Programming– 2D
Problem: given two strings x and y, find the longest common subsequence (LCS) and print its length.
• x : ABCBDAB • y : BDCABC
• “BCAB” is the longest subsequence found in both sequences, so the answer is 4.
Dynamic Programming– 2D
Step 1: Identify the sub-problems (in words). Step 1.1: Identify the original problem.
Let Cnm be the length of the LCS of x1..n and y1..m
Step 1.2: Identify the possible sub-problems. Let Cij be the length of the LCS of x1..i and y1..j
Dynamic Programming– 2D
Step 2: Find the recurrence.
Step 2.1: What decision do I make at every step?.
Two options. To contribute to the LCS length or not.
• If xi = yj , they both contribute to the LCS => match
• If xi != yj , either xi or yj does not contribute to the LCS, so one can be dropped
Dynamic Programming– 2D
Step 2: Find the recurrence.
Step 2.1: What decision do I make at every step?.
Two options. To contribute to the LCS length or not.
• If xi = yj , they both contribute to the LCS => match
• If xi != yj , either xi or yj does not contribute to the LCS, so one can be dropped
Optimal substructures
Dynamic Programming– 2D
• If𝑧! ≠𝑥”,thenwecouldappend𝑥” =𝑦# toZtoobtainacommon subsequence of X and Y of length 𝑘 + 1, contradicting the supposition that Z is a LCS of X and Y.
• The prefix 𝑍!$% is a common subsequence of 𝑋”$% and 𝑌#$% with length k-1. We wish to show that it is an LCS.
• Suppose for the purpose of contradiction that there exists a common subsequence W of Xm-1 and Yn-1 with length greater than k-1. Then, appending 𝑥! = 𝑦” to produce W produces a common subsequence of X and Y whose length is greater than k, which is a contradiction.
Dynamic Programming– 2D
• If 𝑧! ≠ 𝑥”, then Z is a common subsequence of Xm-1 and Y. If there were a common subsequence W of Xm-1 and Y with length greater than k, then W would also be a common subsequence of Xm and Y, contradicting the assumption that Z is an LCS of X and Y.
Dynamic Programming– 2D
• Overlapping
• TofindanLCSofXandY,wemayneedtofindtheLCSsofXandYn-1 and of Xm-1 and Y. But each of these subproblems has the subsubproblem of finding an LCS of Xm-1 and Yn-1.
Dynamic Programming– 2D
Step 2: Find the recurrence.
Step 2.1: What decision do I make at every step?.
Two options. To contribute to the LCS length or not.
• If xi = yj , they both contribute to the LCS => match
• If xi != yj , either xi or yj does not contribute to the LCS, so one can be dropped
Dynamic Programming– 2D
Step 2: Find the recurrence.
• If xi = yj , they both contribute to the LCS => match
• Cij = Ci−1,j−1 + 1
• Otherwise, either xi or yj does not contribute to the LCS, so one can be
• Cij = max{Ci−1,j ,Ci,j−1}
Step 3: Recognize and solve the base cases. • Ci0 =C0j =0.
Dynamic Programming– 2D
Step 4: Implement a solving methodology.
for(i=0;i<=n;i++) c[i][0]=0;
for(j=0;j<=m;j++) c[0][j]=0;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(x[i]==y[j])
c[i][j]=c[i-1][j-1]+1;
c[i][j]=max(c[i-1][j],c[i][j-1])
Dynamic Programming– 2D
Step 4: Implement a solving methodology.
Dynamic Programming– trees
Problem: given a tree, find the size of the Largest Independent Set (LIS). A set of nodes is an independent set if there are no edges between the nodes.
The largest independent set (LIS) is in white. The size of the LIS is 5.
Dynamic Programming– trees
Step 1: Identify the sub-problems (in words). Step 1.1: Identify the original problem.
MIS(r) denote the size of the largest independent set in the tree with root at r.
Step 1.2: Identify the possible sub-problems.
MIS(v) denote the size of the largest independent set in the subtree rooted at v.
Dynamic Programming– trees
Step 2: Find the recurrence.
Step 2.1: What decision do I make at every step?.
Two options.
• Include the node.
• A set that includes v necessarily excludes all of v’s children.
• Do not include the current node (root).
• Any independent set is the union of independent sets in the subtrees rooted at the children of v.
Dynamic Programming– trees
Step 2: Find the recurrence.
Step 2.1: What decision do I make at every step?.
Two options.
• Include the node.
• A set that includes v necessarily excludes all of v’s children.
• Do not include the current node (root).
• Any independent set is the union of independent sets in the subtrees rooted at the
children of v.
children w of v 37 grandchildren x of v
Dynamic Programming– trees
Step 4: Implement a solving methodology.
• What data structure should we use to memoize this recurrence? • Array, 2D array, tree?
• What’s a good order to consider the subproblems?
• The subproblems associated with any node v depends on the subproblems
associated with the children and grandchildren of v.
• We can visit the nodes in any order we like, provided that every vertex is visited
before its parent.
• Pre-order? In-Order? Post-Order?
Dynamic Programming– trees
Step 4: Implement a solving methodology.
• What data structure should we use to memoize this recurrence?
• The most natural choice is the tree itself! Specifically, for each vertex v, we store the result of MIS(v) in a field v.MIS
• What’s a good order to consider the subproblems?
• The subproblems associated with any node v depends on the subproblems
associated with the children and grandchildren of v.
• We can visit the nodes in any order we like, provided that every vertex is visited before its parent.
• Post-Order traversal.
Dynamic Programming– trees
Step 4: Implement a solving methodology.
• We can derive an even simpler algorithm by defining two separate functions over the nodes of the tree.
• Let MISyes(v) denote the size of the largest independent set of the subtree rooted at v that includes v.
• Let MISno(v) denote the size of the largest independent set of the subtree rooted at v that excludes v.
Dynamic Programming– trees
Dynamic Programming– trees
Dynamic Programming– trees
Dynamic Programming– trees
Dynamic Programming– trees
Dynamic Programming– trees
Dynamic Programming– trees
Dynamic Programming– trees
Dynamic Programming– trees
N=0 Y=1 49
Dynamic Programming– trees
N=0 Y=1 50
Dynamic Programming– trees
N=0 Y=1 51
Dynamic Programming– trees
N=0 Y=1 52
Dynamic Programming– trees
N=2 N=0 Y=1 Y=1
N=0 Y=1 53
Dynamic Programming– trees
N=2 N=0 Y=1 Y=1
N=0 Y=1 54
• Complete Search
• Divide and Conquer.
• Dynamic Programming. • Introduction.
• Examples.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com