CS计算机代考程序代写 chain DNA AI assembly algorithm NEW SOUTH WALES

More Dynamic Programming Problems
Balanced Partition You have a set of n integers. Partition these integers into two subsets such that you minimise |S1 − S2|, where S1 and S2 denote the sums of the elements in each of the two subsets.
Solution: Let S be the total sum of all integers in the set; consider the Knapsack problem (with duplicate items not allowed) with the knapsack of size S/2 and with each integer xi of both size and value equal to xi.
Claim: the best packing of such knapsack produces optimally balanced partition, with S1 being all the integers in the knapsack and S2 all the integers left out of the knapsack.
Why? Since S = S1 + S2 we obtain
S − S1 = S1 + S2 − S1 = S2 − S1
222 i.e. S2 − S1 = 2(S/2 − S1).
Thus, minimising S/2 − S1 will minimise S2 − S1.
So, all we have to do is find a subset of these numbers with the largest
possible total sum which fits inside a knapsack of size S/2. COMP3121/3821/9101/9801 17 / 41

Dynamic Programming:
Dynamic Programming: Assembly line scheduling
Example 1: Assembly line scheduling. Instance:
a11
e2
a21
a12
t11 t12
a1(k-1)
a1k
a1(n-1)
a1n
e1
t1(k-1)
t2(k-1)
t1k
t2k
t1(n-1)
t2(n-1)
x1
x2
t21
t22
a2 1
a2(k-1)
a2k
a2(n-1)
a2n
Instance: Two assembly lines with workstations for n jobs.
On the first assembly line the kth job takes a1,k (1 ≤ k ≤ n) units of time to
complete; on the second assembly line the same job takes a2,k units of time. To move the product from station k − 1 on the first assembly line to station k
on the second line it takes t1,k−1 units of time.
Likewise, to move the product from station k − 1 on the second assembly line
to station k on the first assembly line it takes t2,k−1 units of time.
COMP3121/3821/9101/9801 18 / 41
a1k
a1(k-1)

Dynamic Programming:
1(k-2) t1(k-1) t
Dynamic Programming: Assembly line scheduling
Example 1: Assembly line scheduling. Instance:
a11
e2
a21
a12
t11 t12
a1(k-1)
a1k
a1(n-1)
a1n
e1
t1(k-1)
t2(k-1)
t1k
t2k
t1(n-1)
t2(n-1)
x1
x2
t21
t22
a2 1
a2(k-1)
a2k
a2(n-1)
a2n
To bring an unfinished product to the first assembly line it takes e1 units of time.
To bring an unfinished product to the second assembly line it takes e2 units of time.
To get a finished product from the first assembly line to the warehouse it takes x1 units of time;
To get a finished product from the second assembly line to the warehouse it takes x2 units.
Task: Find a fastest way to assemble a product using both lines as necessary.
a1(k-1)
a1k
t
COMP3121/3821/9101/9801 19 / 41

Solution 2: recursion:
Dynamic Programming: Assembly line scheduling
a1, k t1, k-1
t2, k-1
a2, k
For each k ≤ n, we solve subproblems P (1, k) and P (2, k) by a simultaneous recursion on k:
P (1, k) : find the minimal amount of time m(1, k) needed to finish the first k jobs, such the kth job is finished on the kth workstation on the first assembly line;
P (2, k) : find the minimal amount of time m(2, k) needed to finish the first k
jobs, such the kth job is finished on the kth workstation on the second assembly line.
a1. k-1 t1, k-2
t2, k-2
a2, k-1
t1, k
t2, k
COMP3121/3821/9101/9801 20 / 41

DynaEmxiacmPprleog1r:aAmsmseimngbly line scheduling. Instance:
a11
e2
a21
a12
t11 t12
a1(k-1)
a1k
a1(n-1)
a1n
e1
t1(k-1)
t2(k-1)
t1k
t2k
t1(n-1)
t2(n-1)
x1
x2
t21
t22
a2 1
a2(k-1)
a2k
a2(n-1)
a2n
We solve P (1, k) and P (2, k) by a simultaneous recursion: Initially m(1, 1) = e1 + a1,1 and m(2, 1) = e2 + a2,1. Recursion:
m(1,k) = min{m(1,k − 1) + a1,k, m(2,k − 1) + t2,k−1 + a1,k} m(2,k) = min{m(2,k − 1) + a2,k, m(1,k − 1) + t1,k−1 + a2,k}
Finally, after obtaining m(1, n) and m(2, n) we choose
opt = min{m(1, n) + x1, m(2, n) + x2}.
This problem is important because it has the same design logic as the Viterbi
a1k
(k
-2)
1(k-1) t1k
o
dingconvolutiotnalcodesintelecommunicationsetc,covered
a1(k-1)
algorithm, an extremely important algorithm for many fields such as speech
recognition, det1
c
inCOMP4121(AdvanceCdOAMlgPo3r1i2t1h/m38s2)1./9101/9801 21/41

Dynamic Programming: Matrix chain multiplication
For any three matrices of compatible sizes we have A(BC) = (AB)C. Example 2: Matrix chain multiplication.
However, the number of real number multiplications needed to perform in order to obtain the matrix product can be very different:
A=10X 100; B=100X 5; C=5X 50 AB C
50
100 55 50 (AB)C 55 50 10 10 C 10
A
100
A(BC) 10
100 A
50
B
100
To evaluate (AB)C we need
(10×5)×100+(10×50)×5 = 5000+2500 = 7500 multiplications;
To evaluate A(BC) we need
(100 × 50) × 5 + (10 × 50) × 100 = 25000 + 50000 = 75000 multiplications!
COMP3121/3821/9101/9801 22 / 41
BC

Dynamic Programming: Matrix chain multiplication
Problem Instance: A sequence of matrices A1A2…An;
Task: Group them in such a way as to minimise the total number of
multiplications needed to find the product matrix.
The total number of different distributions of brackets is equal to the number
of binary trees with n leaves.
The total number of different distributions of brackets satisfies the following
recursion (why?):
n−1
T(n) = 􏰂 T(i)T(n − i)
i=1
One can show that the solution satisfies T(n) = Ω(2n).
Thus, we cannot do an exhaustive search for the optimal placement of the brackets.
COMP3121/3821/9101/9801 23 / 41

Dynamic Programming: Matrix chain multiplication
Problem Instance: A sequence of matrices A1A2…An;
Task: Group them in such a way as to minimise the total number of
multiplications needed to find the product matrix. The subproblems P (i, j) to be considered are:
“group matrices AiAi+1…Aj−1Aj in such a way as to minimise the total number of multiplications needed to find the product matrix”.
Note: this looks like it is a case of a “2D recursion, but we can actually do it with a simple “linear” recursion.
We group such subproblems by the value of j − i and perform a recursion on the value of j − i.
At each recursive step m we solve all subproblems P (i, j) for which j − i = m.
COMP3121/3821/9101/9801 24 / 41

Dynamic Programming: Matrix chain multiplication
Let m(i,j) denote the minimal number of multiplications needed to compute the product AiAi+1…Aj−1Aj ; let also the size of matrix Ai be si−1 × si.
Recursion: We examine all possible ways to place the principal (outermost) multiplication, splitting the chain into the product (Ai . . . Ak ) · (Ak+1 . . . Aj ).
Note that both k − i < j − i and j − (k + 1) < j − i; thus we have the solutions of the subproblems P (i, k) and P (k + 1, j) already computed and stored in slots k − i and j − (k + 1), respectively, which precede slot j − i we are presently filling. Note also that the matrix product Ai ...Ak is a si−1 × sk matrix L and Ak+1 ...Aj is a sk ×sj matrix R. To multiply an si−1 × sk matrix L and an sk × sj matrix R it takes si−1sksj many multiplications: sk si-1 sj sj L sk = si-1 R LXR Total number of multiplications: Si-1 Sj Sk COMP3121/3821/9101/9801 25 / 41 Dynamic Programming: Matrix chain multiplication The recursion: m(i,j)=min{m(i,k)+m(k+1,j)+si−1sjsk : i≤k≤j−1} Note that the recursion step is a brute force search but the whole algorithm is not, because all the subproblems are solved only once, and there are only O(n2) many such subproblems. k for which the minimum in the recursive definition of m(i,j) is achieved can be stored to retrieve the optimal placement of brackets for the whole chain A1 ...An. Thus, in the mth slot of the table we are constructing we store all pairs (m(i, j), k) for which j − i = m. COMP3121/3821/9101/9801 26 / 41 Dynamic Programming: Longest Common Subsequence Assume we want to compare how similar two sequences of symbols S and S∗ are. Example: how similar are the genetic codes of two viruses. This can tell us if one is just a genetic mutation of the other. A sequence s is a subsequence of another sequence S if s can be obtained by deleting some of the symbols of S (while preserving the order of the remaining symbols). Given two sequences S and S∗ a sequence s is a Longest Common Subsequence of S,S∗ if s is a common subsequence of both S and S∗ and is of maximal possible length. COMP3121/3821/9101/9801 27 / 41 Dynamic Programming: Longest Common Subsequence Instance: Two sequences S = ⟨a1,a2,...an⟩ and S∗ = ⟨b1,b2,...,bm⟩. Task: Find a longest common subsequence of S,S∗. We first find the length of the longest common subsequence of S,S∗. “2Drecursion”: forall1≤i≤nandall1≤j≤mletc[i,j]bethelengthof the longest common subsequence of the truncated sequences Si = ⟨a1,a2,...ai⟩ and Sj∗ = ⟨b1,b2,...,bj⟩. Recursion: we fill the table row by row, so the ordering of subproblems is the lexicographical ordering; 0, c[i,j] = c[i−1,j −1]+1 max{c[i − 1,j],c[i,j − 1]} if i=0orj=0; if i,j > 0 and ai = bj; if i,j > 0 and ai ̸= bj.
COMP3121/3821/9101/9801 28 / 41

Dynamic Programming: Longest Common Subsequence
!
Retrieving a longest common subsequence:
!!
COMP3121/3821/9101/9801 29 / 41

Dynamic Programming: Longest Common Subsequence
What if we have to find a longest common subsequence of three sequences S1, S2, S3?
Can we do LCS(LCS(S1,S2),S3)? Not necessarily! Consider
S1 = ABCDEGG S2 =ACBEEFG S3 = ACCEDGF
LCS(LCS(S1, S2), S3) LCS(LCS(S2, S3), S1) LCS(LCS(S1, S3), S2)
But
LCS(S1, S2) = ABEG LCS(S2, S3) = ACEF LCS(S1, S3) = ACDG
= LCS(ABEG, ACCEDGF ) = AEG = LCS(ACEF, ABCDEGG) = ACE = LCS(ACDG, ACBEEF G) = ACG
LCS(S1, S2, S3) = ACEG
So how would you design an algorithm which computes correctly LCS(S1,S2,S3)?
COMP3121/3821/9101/9801
30 / 41

Dynamic Programming: Longest Common Subsequence
Instance: Three sequences S = ⟨a1,a2,…an⟩, S∗ = ⟨b1,b2,…,bm⟩ and S∗∗ = ⟨c1,c2,…,ck⟩.
Task: Find a longest common subsequence of S, S∗, S∗∗.
We again first find the length of the longest common subsequence of S,S∗,S∗∗.
for all 1 ≤ i ≤ n, all 1 ≤ j ≤ m and all l ≤ k, let d[i, j, l] be the length of the
longest common subsequence of the truncated sequences Si = ⟨a1 , a2 , . . . ai ⟩,
S∗ = ⟨b1,b2,…,bj⟩ and S∗∗ = ⟨c1,c2,…,cl⟩. jl
Recursion:
0,
d[i,j,l]= d[i−1,j−1,l−1]+1
max{d[i − 1, j, l], d[i, j − 1, l], d[i, j, l − 1]}
if i=0orj=0orl=0; ifi,j,l>0andai =bj =cl; otherwise.
COMP3121/3821/9101/9801
31 / 41

Dynamic Programming: Shortest Common Supersequence
Instance: Two sequences s = ⟨a1,a2,…an⟩ and s∗ = ⟨b1,b2,…,bm⟩. Task: Find a shortest common super-sequence S of s,s∗, i.e., the shortest
possible sequence S such that both s and s∗ are subsequences of S.
Solution: Find the longest common subsequence LCS(s,s∗) of s and s∗ and then add differing elements of the two sequences at the right places, in any order; for example:
s =abacada s∗ =xbycazd
LCS(s, s∗) =bcad shortest super-sequence S =axbyacazda
COMP3121/3821/9101/9801
32 / 41

Dynamic Programming: Edit Distance
Edit Distance Given two text strings A of length n and B of length m, you want to transform A into B. You are allowed to insert a character, delete a character and to replace a character with another one. An insertion costs cI , a deletion costs cD and a replacement costs cR.
Task: find the lowest total cost transformation of A into B.
Note: if all operations have a unit cost, then you are looking for the minimal number of such operations required to transform A into B; this number is called the edit distance between A and B.
If the sequences are sequences of DNA bases and the costs reflect the probabilities of the corresponding mutations, then the minimal cost represents the probability that one sequence mutates into another sequence in the course of DNA copying.
Subproblems: Let C(i,j) be the minimum cost of transforming the sequence A[1..i] into the sequence B[1..j] for all i ≤ n and all j ≤ m.
COMP3121/3821/9101/9801 33 / 41

Dynamic Programming: Edit Distance
Subproblems P(i,j): Find the minimum cost C(i,j) of transforming the sequence A[1..i] into the sequence B[1..j] for all i ≤ n and all j ≤ m.
Recursion: we again fill the table of solutions C(i, j) for subproblems P (i, j) row by row (why is this OK?):
C(i−1,j)+cD
C(i, j − 1) + cI C(i,j)=min 􏰁
 C(i−1,j−1) if A[i]=B[j]  C(i−1,j−1)+cR if A[i]̸=B[j]
cost cD + C(i − 1, j) corresponds to the option if you recursively transform A[1..i − 1] into B[1..j] and then delete A[i];
costC(i,j−1)+cI correspondstotheoptionifyoufirsttransformA[1..i]to B[1..j − 1] and then append B[j] at the end;
the third option corresponds to first transforming A[1..i − 1] to B[1..j − 1] and
1 if A[i] is already equal to B[j] do nothing, thus incurring a cost of
only C(i − 1, j − 1);
2 if A[i] is not equal to B[j] replace A[i] by B[j] with a total cost of
C(i − 1, j − 1) + cR.
COMP3121/3821/9101/9801 34 / 41

Dynamic Programming: Maximizing an expression
Instance: a sequence of numbers with operations +, −, × in between, for example 1+2−3×6−1−2×3−5×7+2−8×9
Task: Place brackets in a way that the resulting expression has the largest possible value.
What will be the subproblems?
Maybe for a subsequence of numbers A[i..j] place the brackets so that the resulting expression is maximised?
maybe we could consider which the principal operations should be, i.e.
A[i..k] ⊙ A[k + 1..j]. Here ⊙ is whatever operation is between A[k] and A[k + 1].
But when would such expression be maximised if there could be both positive and negative values for A[i..k] and A[k + 1..j] depending on the placement of brackets??
Maybe we should look for placements of brackets not only for the maximal value but also for the minimal value!
Exercise: write the exact recursion for this problem.
COMP3121/3821/9101/9801 35 / 41

Dynamic Programming: Turtle Tower
Instance: You are given n turtles, and for each turtle you are given its weight and its strength. The strength of a turtle is the maximal weight you can put on it without cracking its shell.
Task: Find the largest possible number of turtles which you can stack one on top of the other, without cracking any turtle.
Hint: Order turtles in an increasing order of the sum of their weight and their strength, and proceed by recursion.
You can find a solution to this problem and of another interesting problem on the class website (class resources, file “More Dynamic Programming”).
COMP3121/3821/9101/9801 36 / 41

Dynamic Programming: Bellman Ford algorithm
One of the earliest use of Dynamic Programming (1950’s) invented by Bellman. Instance: A directed weighted graph G = (V, E) with weights which can be
negative, but without cycles of negative total weight and a vertex s ∈ V . Goal: Find the shortest path from vertex s to every other vertex t.
Solution: Since there are no negative weight cycles, the shortest path cannot contain cycles, because a cycle can be excised to produce a shorter path.
Thus, every shortest path can have at most |V | − 1 edges.
Subproblems: For every v ∈ V and every i, (1 ≤ i ≤ n − 1), let opt(i,v) be
the length of a shortest path from s to v which contains at most i edges. Our goal is to find for every vertex t ∈ G the value of opt(n − 1,t) and the
path which achieves such a length.
Note that if the shortest path from a vertex v to t is (v,p1,p2,…,pk,t) then (p1,p2,…,pk,t) must be the shortest path from p1 to t, and (v,p1,p2,…,pk) must also be the shortest path from v to pk.
COMP3121/3821/9101/9801 37 / 41

Dynamic Programming: Bellman Ford algorithm
Let us denote the length of the shortest path from s to v among all paths which contain at most i edges by opt(i, v), and let pred(i, v) be the immediate predecessor of vertex v on such shortest path.
Recursion:
opt(i, v) = min(opt(i − 1, v), min{opt(i − 1, p) + w(e(p, v))}; p∈V
􏰁pred(i − 1, v) if minp∈V {opt(i − 1, p) + w(e(p, v))} ≥ opt(i − 1, v) pred(i, v) = arg minp∈V {opt(i − 1, p) + w(e(p, v))} otherwise
(here w(e(p, v)) is the weight of the edge e(p, v) from vertex p to vertex v.)
Final solutions: p(n − 1, v) for all v ∈ G.
Computation opt(i, v) runs in time O(|V | × |E|), because i ≤ |V | − 1 and for each v, min is taken over all edges e(p, v) incident to v; thus in each round all edges are inspected.
Algorithm produces shortest paths from s to every other vertex in the graph.
The method employed is sometimes called “relaxation”, because we progressively relax the additional constraint on how many edges the shortest paths can contain.
COMP3121/3821/9101/9801 38 / 41

Dynamic Programming: Floyd Warshall algorithm
Let again G = (V,E) be a directed weighted graph where V = {v1,v2,…,vn} and where weights w(e(vp,vq)) of edges e(vp,vq) can be negative, but there are no negative weight cycles.
We can use a somewhat similar idea to obtain the shortest paths from every vertex vp to every vertex vq (including back to vp).
Let opt(k,vp,vq) be the length of the shortest path from a vertex vp to a vertex vq such that all intermediate vertices are among vertices {v1,v2,…,vk}, (1 ≤ k ≤ n).
Then
opt(k,vp,vq) = min{opt(k − 1,vp,vq),opt(k − 1,vp,vk) + opt(k − 1,vk,vq)}
Thus, we gradually relax the constraint that the intermediary vertices have to belong to {v1,v2,…,vk}.
Algorithm runs in time |V |3.
COMP3121/3821/9101/9801 39 / 41

Another example of relaxation:
Compute the number of partitions of a positive integer n. That is to say the number of distinct multi-sets of positive integers {n1, . . . , nk} which sumupton,i.e.,suchthatn1+…+nk =n.
Note: multi-sets means that the set can contain several copies of the same number, but all permutations of elements count as a single multi-set.
Hint: Let nump(i, j) denotes the number of partitions {j1, . . . , jp} of j, i.e., the number of sets such that j1 + . . . + jp = j which, in addition, have the property that every element jq of each partition satisfies jq ≤ i. We are looking for nump(n, n) but the recursion is based on relaxation of the allowed size i of the parts of j for all i, j ≤ n. To get a recursive definition of nump(i,j) distinguish the case of partitions where all components are ≤ i − 1 and the case where at least one component is of size i.
COMP3121/3821/9101/9801 40 / 41

PUZZLE
You have 2 lengths of fuse that are guaranteed to burn for precisely 1 minute each. Other than that fact, you know nothing; they may burn at different (indeed, at variable) rates, they may be of different lengths, thick nesses, materials, etc. How can you use these two fuses to time a 45 second interval?
COMP3121/3821/9101/9801 41 / 41