程序代写代做代考 C algorithm data structure Algorithms Week 6

Algorithms Week 6
Ljubomir Perkovi ́c, DePaul University

Dynamic Programming
The basic idea behind dynamic programming is recursion without repetition.
To develop a dynamic algorithm:

Dynamic Programming
The basic idea behind dynamic programming is recursion without repetition.
To develop a dynamic algorithm:
1 Formulate the problem recursively

Dynamic Programming
The basic idea behind dynamic programming is recursion without repetition.
To develop a dynamic algorithm:
1 Formulate the problem recursively
a Describe the problem that you want to solve recursively
b Give a clear recursive formula or algorithm
2 Build solutions to your recurrence from the bottom up
a Identify the subproblems
b Choose a memoization data structure

Subset sum
Subset sum is a classic problem:
Input: An array X[1..n] of positive integers and an integer
T.
Output: A subset of X that sums to T.

Subset sum
Subset sum is a classic problem:
Input:
Output: Example:
An array X[1..n] of positive integers and an integer T.
A subset of X that sums to T. Let X = [4,7,6,3,1] and T = 10.

Subset sum
Subset sum is a classic problem:
Input:
Output: Example:
An array X[1..n] of positive integers and an integer T.
A subset of X that sums to T. Let X = [4,7,6,3,1] and T = 10.
• 4+6=10,so{4,6}isavalidsolution.

Dynamic programming algorithm development step 1
To develop a dynamic algorithm, first formulate the problem recursively
a Describe the problem that you want to solve recursively
b Give a clear recursive formula or algorithm
Define SS(i,t) to be True if some subset of X[i..n] sums to t. Then
SS(i,t) =
True,
False,
SS (i + 1, t ),
SS(i +1,t)∨SS(i +1,t −X[i]),
if t = 0
if i > n
if t < X [i ] otherwise Dynamic programming algorithm development step 1 To develop a dynamic algorithm, first formulate the problem recursively a Describe the problem that you want to solve recursively b Give a clear recursive formula or algorithm Define SS(i,t) to be True if some subset of X[i..n] sums to t. Then True, False, SS (i + 1, t ), SS(i +1,t)∨SS(i +1,t −X[i]), We want to compute SS(1,T). if t = 0 if i > n
if t < X [i ] otherwise SS(i,t) = Dynamic programming algorithm development step 2 Build solutions to your recurrence from the bottom up a Recursive subproblems are of type SS(i,t) where 1 ≤ i ≤ n + 1 and 0 ≤ t ≤ T ... Dynamic programming algorithm development step 2 Build solutions to your recurrence from the bottom up a Recursive subproblems are of type SS(i,t) where 1 ≤ i ≤ n + 1 and 0 ≤ t ≤ T ... b ... so we need a two-dimensional array SS[1..n+1, 0..T]. Dynamic programming algorithm development step 2 Build solutions to your recurrence from the bottom up a Recursive subproblems are of type SS(i,t) where 1 ≤ i ≤ n + 1 and 0 ≤ t ≤ T ... b ... so we need a two-dimensional array SS[1..n+1, 0..T]. c Each entry SS[i,t] depends only on entries SS(i+1, t) and SS(i+1, t-X[i]) ... 0 t−X[i] t T 1 i i+1 n+1 Dynamic programming algorithm development step 2 Build solutions to your recurrence from the bottom up a Recursive subproblems are of type SS(i,t) where 1 ≤ i ≤ n + 1 and 0 ≤ t ≤ T ... b ... so we need a two-dimensional array SS[1..n+1, 0..T]. c Each entry SS[i,t] depends only on entries SS(i+1, t) and SS(i+1, t-X[i]) ... 0 t−X[i] t T 1 i i+1 n+1 d ... so we need to fill the 2D-array row-by-row bottom-up. Dynamic programming algorithm development step 2 Build solutions to your recurrence from the bottom up a Recursive subproblems are of type SS(i,t) where 1 ≤ i ≤ n + 1 and 0 ≤ t ≤ T ... b ... so we need a two-dimensional array SS[1..n+1, 0..T]. c Each entry SS[i,t] depends only on entries SS(i+1, t) and SS(i+1, t-X[i]) ... 0 t−X[i] t T 1 i i+1 n+1 d ... so we need to fill the 2D-array row-by-row bottom-up. FastSubsetSum (via dynamic programming) FastSubsetSum(X[1..n], T): S[n+1, 0] ← True for t ← 1 to T S[n+1, t] ← False for i ←n downto 1 S[i, 0] ← True for t ← 1 to X[i] - 1 S[i, t] ← S[i+1, t] for t ← X[i] to T S[i, t] ← S[i+1, t] ∨ S[i+1, t-X[i]] return S[1, T] FastSubsetSum (via dynamic programming) FastSubsetSum(X[1..n], T): S[n+1, 0] ← True for t ← 1 to T S[n+1, t] ← False for i ←n downto 1 S[i, 0] ← True for t ← 1 to X[i] - 1 S[i, t] ← S[i+1, t] for t ← X[i] to T S[i, t] ← S[i+1, t] ∨ S[i+1, t-X[i]] return S[1, T] Running time? FastSubsetSum (via dynamic programming) FastSubsetSum(X[1..n], T): S[n+1, 0] ← True for t ← 1 to T S[n+1, t] ← False for i ←n downto 1 S[i, 0] ← True for t ← 1 to X[i] - 1 S[i, t] ← S[i+1, t] for t ← X[i] to T S[i, t] ← S[i+1, t] ∨ S[i+1, t-X[i]] return S[1, T] Running time? O(nT) Edit distance The edit distance between two strings is the minimum number of • letter insertions, • letter deletions, and • letter substitutions required to transform one string into the other. Edit distance The edit distance between two strings is the minimum number of • letter insertions, • letter deletions, and • letter substitutions required to transform one string into the other. For example, the edit distance between FOOD and MONEY is 4: FOOD Edit distance The edit distance between two strings is the minimum number of • letter insertions, • letter deletions, and • letter substitutions required to transform one string into the other. For example, the edit distance between FOOD and MONEY is 4: MOOD Edit distance The edit distance between two strings is the minimum number of • letter insertions, • letter deletions, and • letter substitutions required to transform one string into the other. For example, the edit distance between FOOD and MONEY is 4: MOOD Edit distance The edit distance between two strings is the minimum number of • letter insertions, • letter deletions, and • letter substitutions required to transform one string into the other. For example, the edit distance between FOOD and MONEY is 4: MOND Edit distance The edit distance between two strings is the minimum number of • letter insertions, • letter deletions, and • letter substitutions required to transform one string into the other. For example, the edit distance between FOOD and MONEY is 4: MONED Edit distance The edit distance between two strings is the minimum number of • letter insertions, • letter deletions, and • letter substitutions required to transform one string into the other. For example, the edit distance between FOOD and MONEY is 4: MONEY Edit distance Formal problem specification: Input: Two strings A[1..m] and B[1..n] Output: The edit distance between A and B Edit distance The edit distance between ALGORITHM and ALTRUISTIC, using another kind of visualization: Edit distance The edit distance between ALGORITHM and ALTRUISTIC, using another kind of visualization: ALGOR I THM AL TRUISTIC Edit distance The edit distance between ALGORITHM and ALTRUISTIC, using another kind of visualization: ALGOR I THM AL TRUISTIC Columns with • a gap in the top word represent the insertion of a letter Edit distance The edit distance between ALGORITHM and ALTRUISTIC, using another kind of visualization: ALGOR I THM AL TRUISTIC Columns with • a gap in the top word represent the insertion of a letter • a gap in the bottom word represents the deletion of a letter Edit distance The edit distance between ALGORITHM and ALTRUISTIC, using another kind of visualization: ALGOR I THM AL TRUISTIC Columns with • a gap in the top word represent the insertion of a letter • a gap in the bottom word represents the deletion of a letter • with two different characters correspond to substitutions Recursive structure To develop a dynamic algorithm: 1 Formulate the problem recursively Recursive structure To develop a dynamic algorithm: 1 Formulate the problem recursively a Describe the problem that you want to solve recursively Recursive structure To develop a dynamic algorithm: 1 Formulate the problem recursively a Describe the problem that you want to solve recursively ALGOR I THM AL TRUISTIC If we remove the last column, Recursive structure To develop a dynamic algorithm: 1 Formulate the problem recursively a Describe the problem that you want to solve recursively ALGOR I TH AL TRUISTI If we remove the last column, Recursive structure To develop a dynamic algorithm: 1 Formulate the problem recursively a Describe the problem that you want to solve recursively ALGOR I TH AL TRUISTI If we remove the last column, the remaining columns must represent the shortest edit sequence for the remaining prefixes. Recursive structure To develop a dynamic algorithm: 1 Formulate the problem recursively a Describe the problem that you want to solve recursively ALGOR I TH AL TRUISTI If we remove the last column, the remaining columns must represent the shortest edit sequence for the remaining prefixes. In other words, once we decide what should happen in the last column, the recursion fairy will figure out the rest. Recursive structure To develop a dynamic algorithm: 1 Formulate the problem recursively a Describe the problem that you want to solve recursively ALGOR I TH AL TRUISTI If we remove the last column, the remaining columns must represent the shortest edit sequence for the remaining prefixes. In other words, once we decide what should happen in the last column, the recursion fairy will figure out the rest. Let Edit(i,j) be the edit distance between A[1..i] and B[1..j]. Insertion So what can happen in the last column in general? Insertion So what can happen in the last column in general? ALGOR ALTRU Insertion So what can happen in the last column in general? ALGOR ALTR U An insertion, i.e. the last entry in top row is empty. Insertion So what can happen in the last column in general? ALGOR ALTR U An insertion, i.e. the last entry in top row is empty. Then Edit (i , j ) = 1 + Edit (i , j − 1) Deletion So what can happen in the last column in general? Deletion So what can happen in the last column in general? ALGOR ALTRU Deletion So what can happen in the last column in general? ALGO R ALTRU A deletion, i.e. the last entry in bottom row is empty. Deletion So what can happen in the last column in general? ALGO R ALTRU A deletion, i.e. the last entry in bottom row is empty. Then Edit (i , j ) = 1 + Edit (i − 1, j ) Substitution So what can happen in the last column in general? Substitution So what can happen in the last column in general? ALGOR ALTRU Substitution So what can happen in the last column in general? ALGO R ALTR U A substitution, i.e. the last entry in both rows is non-empty. Substitution So what can happen in the last column in general? ALGO R ALTR U A substitution, i.e. the last entry in both rows is non-empty. Then Edit (i , j ) = 1 + Edit (i − 1, j − 1) if the characters are different. Substitution So what can happen in the last column in general? Substitution So what can happen in the last column in general? ALGOR ALTR Substitution So what can happen in the last column in general? ALGO R ALT R A substitution, i.e. the last entry in both rows is non-empty. Substitution So what can happen in the last column in general? ALGO R ALT R A substitution, i.e. the last entry in both rows is non-empty. Then Edit (i , j ) = Edit (i − 1, j − 1) if the characters are the same. The substitution is free. Edit function recurrence To develop a dynamic algorithm: 1 Formulate the problem recursively a Describe the problem that you want to solve recursively b Give a clear recursive formula or algorithm Edit(i,j) is the edit distance between A[1..i] and B[1..j]. Edit function recurrence To develop a dynamic algorithm: 1 Formulate the problem recursively a Describe the problem that you want to solve recursively b Give a clear recursive formula or algorithm Edit(i,j) is the edit distance between A[1..i] and B[1..j]. i, if j = 0  Edit(i,j) =  Edit function recurrence To develop a dynamic algorithm: 1 Formulate the problem recursively a Describe the problem that you want to solve recursively b Give a clear recursive formula or algorithm Edit(i,j) is the edit distance between A[1..i] and B[1..j]. i, if j = 0  j, if i = 0  Edit(i,j) =   Edit function recurrence To develop a dynamic algorithm: 1 Formulate the problem recursively a Describe the problem that you want to solve recursively b Give a clear recursive formula or algorithm Edit(i,j) is the edit distance between A[1..i] and B[1..j]. i,   j, Edit (i , j ) =  if j = 0 if i = 0     min   Edit (i , j − 1) + 1 Edit function recurrence To develop a dynamic algorithm: 1 Formulate the problem recursively a Describe the problem that you want to solve recursively b Give a clear recursive formula or algorithm Edit(i,j) is the edit distance between A[1..i] and B[1..j]. i, if j = 0   j, if i = 0 Edit (i , j ) =  Edit (i , j − 1) + 1    min Edit(i −1,j)+1   Edit function recurrence To develop a dynamic algorithm: 1 Formulate the problem recursively a Describe the problem that you want to solve recursively b Give a clear recursive formula or algorithm Edit(i,j) is the edit distance between A[1..i] and B[1..j]. i,   j, Edit (i , j ) =     min  Edit (i , j − 1) + 1  Edit(i − 1, j) + 1 Edit(i − 1, j − 1) + [A[i] ̸= B[j]] if j = 0 if i = 0 otherwise Dynamic programming algorithm development step 2 Build solutions to your recurrence from the bottom up a Recursive subproblems are Edit(i,j) with 0 ≤ i ≤ m and 0≤j ≤n ... Dynamic programming algorithm development step 2 Build solutions to your recurrence from the bottom up a Recursive subproblems are Edit(i,j) with 0 ≤ i ≤ m and 0≤j ≤n ... b ... so we need a two-dimensional array Edit[0..m, 0..n]. Dynamic programming algorithm development step 2 Build solutions to your recurrence from the bottom up a Recursive subproblems are Edit(i,j) with 0 ≤ i ≤ m and 0≤j ≤n ... b ... so we need a two-dimensional array Edit[0..m, 0..n]. c Each entry Edit[i,j] depends only on entries Edit[i-1,j], Edit[i,j-1], and Edit[i-1,j-1] ... 0j−1jn 0 i−1 i m Dynamic programming algorithm development step 2 Build solutions to your recurrence from the bottom up a Recursive subproblems are Edit(i,j) with 0 ≤ i ≤ m and 0≤j ≤n ... b ... so we need a two-dimensional array Edit[0..m, 0..n]. c Each entry Edit[i,j] depends only on entries Edit[i-1,j], Edit[i,j-1], and Edit[i-1,j-1] ... 0j−1jn 0 i−1 i m d ... so we need to fill the two-dimensional array top-down left-to-right. Dynamic programming algorithm development step 2 Build solutions to your recurrence from the bottom up a Recursive subproblems are Edit(i,j) with 0 ≤ i ≤ m and 0≤j ≤n ... b ... so we need a two-dimensional array Edit[0..m, 0..n]. c Each entry Edit[i,j] depends only on entries Edit[i-1,j], Edit[i,j-1], and Edit[i-1,j-1] ... 0j−1jn 0 i−1 i m d ... so we need to fill the two-dimensional array top-down left-to-right. Edit distance dynamic programming algorithm EditDistance(A[1 .. m], B[1 .. n]): for j ← 0 to n Edit[0, j] ← j for i ← 1 to m Edit[i, 0] ← i for j ← 1 to n ins ← Edit[i, j-1] + 1 del ← Edit[i-1, j] + 1 if A[i] = B[j] rep ← Edit[i-1, j-1] else rep ← Edit[i-1, j-1] + 1 Edit[i, j] ← min{ins, del, rep} return Edit[m, n] Edit distance dynamic programming algorithm EditDistance(A[1 .. m], B[1 .. n]): for j ← 0 to n Edit[0, j] ← j for i ← 1 to m Edit[i, 0] ← i for j ← 1 to n ins ← Edit[i, j-1] + 1 del ← Edit[i-1, j] + 1 if A[i] = B[j] rep ← Edit[i-1, j-1] else rep ← Edit[i-1, j-1] + 1 Edit[i, j] ← min{ins, del, rep} return Edit[m, n] Running time? Edit distance dynamic programming algorithm EditDistance(A[1 .. m], B[1 .. n]): for j ← 0 to n Edit[0, j] ← j for i ← 1 to m Edit[i, 0] ← i for j ← 1 to n ins ← Edit[i, j-1] + 1 del ← Edit[i-1, j] + 1 if A[i] = B[j] rep ← Edit[i-1, j-1] else rep ← Edit[i-1, j-1] + 1 Edit[i, j] ← min{ins, del, rep} return Edit[m, n] Running time? O(mn) Activity Selection Problem Suppose activities 1, 2, . . . , n are scheduled at different times of a single day. Activity Selection Problem Suppose activities 1, 2, . . . , n are scheduled at different times of a single day. Each activity i is has start time si and finish time fi such that si < fi ; activity i can be represented as (si , fi ). Activity Selection Problem Suppose activities 1, 2, . . . , n are scheduled at different times of a single day. Each activity i is has start time si and finish time fi such that si < fi ; activity i can be represented as (si , fi ). Two activities (si , fi ) and (sj , fj ) are compatible if they do not overlap, i.e. if either fj < si or fi < sj . Activity Selection Problem Suppose activities 1, 2, . . . , n are scheduled at different times of a single day. Each activity i is has start time si and finish time fi such that si < fi ; activity i can be represented as (si , fi ). Two activities (si , fi ) and (sj , fj ) are compatible if they do not overlap, i.e. if either fj < si or fi < sj . Goal: choose the largest possible set of compatible activities. Activity Selection Problem Input: List of activities 1, 2, 3, ..., n scheduled at time intervals (s1, f1), (s2, f2), . . . , (sn, fn). Output: The largest possible set of compatible activities. Activity Selection Problem Input: List of activities 1, 2, 3, ..., n scheduled at time intervals (s1, f1), (s2, f2), . . . , (sn, fn). Output: The largest possible set of compatible activities. Solution via recursive backtracking: If activity i is in an optimal solution Activity Selection Problem Input: List of activities 1, 2, 3, ..., n scheduled at time intervals (s1, f1), (s2, f2), . . . , (sn, fn). Output: The largest possible set of compatible activities. Solution via recursive backtracking: If activity i is in an optimal solution then so is the optimal solution for the set of activities that end before si Activity Selection Problem Input: List of activities 1, 2, 3, ..., n scheduled at time intervals (s1, f1), (s2, f2), . . . , (sn, fn). Output: The largest possible set of compatible activities. Solution via recursive backtracking: If activity i is in an optimal solution then so is the optimal solution for the set of activities that end before si and the optimal solution the set of activities that start after fi . Activity Selection Problem Input: List of activities 1, 2, 3, ..., n scheduled at time intervals (s1, f1), (s2, f2), . . . , (sn, fn). Output: The largest possible set of compatible activities. Solution via recursive backtracking: If activity i is in an optimal solution then so is the optimal solution for the set of activities that end before si and the optimal solution the set of activities that start after fi . Running time: O(2n) Activity Selection Problem Input: List of activities 1, 2, 3, ..., n scheduled at time intervals (s1, f1), (s2, f2), . . . , (sn, fn). Output: The largest possible set of compatible activities. Solution via dynamic programming: If activity i is in an optimal solution then so is the optimal solution for the set of activities that end before si and the optimal solution the set of activities that start after fi . Running time: O(n3) Activity Selection Problem Input: List of activities 1, 2, 3, ..., n scheduled at time intervals (s1, f1), (s2, f2), . . . , (sn, fn). Output: The largest possible set of compatible activities. Solution via the greedy method: Running time: O(n log n) The greedy method We try “greedy” approaches: The greedy method We try “greedy” approaches: • Choose activity that starts earliest... The greedy method We try “greedy” approaches: • Choose activity that starts earliest... The greedy method We try “greedy” approaches: • Choose activity that starts earliest... • Choose activity that finishes earliest... The greedy method We try “greedy” approaches: • Choose activity that starts earliest... • Choose activity that finishes earliest... The greedy method We try “greedy” approaches: • Choose activity that starts earliest... • Choose activity that finishes earliest... The greedy method We try “greedy” approaches: • Choose activity that starts earliest... • Choose activity that finishes earliest... The greedy method We try “greedy” approaches: • Choose activity that starts earliest... • Choose activity that finishes earliest... The greedy method We try “greedy” approaches: • Choose activity that starts earliest... • Choose activity that finishes earliest... Seems to be working... The greedy method We try “greedy” approaches: • Choose activity that starts earliest... • Choose activity that finishes earliest... Seems to be working... but we have to prove this. The greedy method We try “greedy” approaches: • Choose activity that starts earliest... • Choose activity that finishes earliest... Seems to be working... but we have to prove this. Assuming activites are sorted by finishing time, we need to show that: 1 There exists a largest set A of compatible activities containing activity 1. The greedy method We try “greedy” approaches: • Choose activity that starts earliest... • Choose activity that finishes earliest... Seems to be working... but we have to prove this. Assuming activites are sorted by finishing time, we need to show that: 1 There exists a largest set A of compatible activities containing activity 1. 2 If A is a largest set of activities containing 1 then A − {1} is a largest set of compatible activities for {(si , fi ) : si ≥ f1}. Condition 1 proof 1 There exists a largest set A of compatible activities containing activity 1. Condition 2 proof 1 There exists a largest set A of compatible activities containing activity 1. 2 If A is a largest set of activities containing 1 then A − {1} is a largest set of compatible activities for {(si , fi ) : si ≥ f1}. GreedyASP Let s be an array of activity starting times and let f be an array of activity finishing times, both sorted by finishing time. In other words, f [1] ≤ f [2] ≤ · · · ≤ f [n]. GreedyASP Let s be an array of activity starting times and let f be an array of activity finishing times, both sorted by finishing time. In other words, f [1] ≤ f [2] ≤ · · · ≤ f [n]. GreedyASP(s,f,n) A ← {1} j←1 for i ← 2 to n if s[i] ≥ f[j] then A ← A U {i} j←i return A GreedyASP Let s be an array of activity starting times and let f be an array of activity finishing times, both sorted by finishing time. In other words, f [1] ≤ f [2] ≤ · · · ≤ f [n]. GreedyASP(s,f,n) A ← {1} j←1 for i ← 2 to n if s[i] ≥ f[j] then A ← A U {i} j←i return A Running time? GreedyASP Let s be an array of activity starting times and let f be an array of activity finishing times, both sorted by finishing time. In other words, f [1] ≤ f [2] ≤ · · · ≤ f [n]. GreedyASP(s,f,n) A ← {1} j←1 for i ← 2 to n if s[i] ≥ f[j] then A ← A U {i} j←i return A Running time? Θ(n), but only if not including the Θ(n log n) time required to sort s and f . Greedy algorithm A problem can be solved using a greedy algorithm if it satisfies these conditions: Greedy choice property: the optimal solution can be constructed from locally optimal choices. This must always be proved before you construct a greedy algorithm for the problem. Optimal substructure: The optimal solutions contain the optimal solutions to its subproblems.

Related Posts