Longestcommonsubsequence

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Longest common subsequence,INPUT: two strings,OUTPUT: longest common subsequence,ACTGAACTCTGTGCACT,TGACTCAGCACAAAAAC,1,Longest common subsequence,INPUT: two strings,OUTPUT: longest common subsequence,AC,TGA,A,CTC,T,G,TG,CAC,T,TGACTC,A,GCAC,AAAAAC,2,Longest common subsequence,If the sequences end with the same,symbol s, then LCS ends with s.,s,s,3,Longest common subsequence,Sequences x,1,x,n, and y,1,y,m,LCS(i,j) = length of a longest common,subsequence of x,1,x,i,and y,1,y,j,4,Longest common subsequence,Sequences x,1,x,n, and y,1,y,m,LCS(i,j) = length of a longest common,subsequence of x,1,x,i,and y,1,y,j,if x,i,= y,j,then,LCS(i,j) =,5,Longest common subsequence,Sequences x,1,x,n, and y,1,y,m,LCS(i,j) = length of a longest common,subsequence of x,1,x,i,and y,1,y,j,if x,i,= y,j,then,LCS(i,j) = 1 + LCS(i-1,j-1),6,Longest common subsequence,Sequences x,1,x,n, and y,1,y,m,LCS(i,j) = length of a longest common,subsequence of x,1,x,i,and y,1,y,j,if x,i,y,j,then,LCS(i,j) = max (LCS(i-1,j),LCS(i,j-1),x,i,and y,j,cannot both be in LCS,7,Longest common subsequence,Sequences x,1,x,n, and y,1,y,m,LCS(i,j) = length of a longest common,subsequence of x,1,x,i,and y,1,y,j,if x,i,y,j,then,LCS(i,j) = max (LCS(i-1,j),LCS(i,j-1),if x,i,= y,j,then,LCS(i,j) = 1 + LCS(i-1,j-1),8,Longest common subsequence,Sequences x,1,x,n, and y,1,y,m,LCS(i,j) = length of a longest common,subsequence of x,1,x,i,and y,1,y,j,if x,i,y,j,then,LCS(i,j) = max (LCS(i-1,j),LCS(i,j-1),if x,i,= y,j,then,LCS(i,j) = 1 + LCS(i-1,j-1),Running time ?,9,Longest common subsequence,Sequences x,1,x,n, and y,1,y,m,LCS(i,j) = length of a longest common,subsequence of x,1,x,i,and y,1,y,j,if x,i,y,j,then,LCS(i,j) = max (LCS(i-1,j),LCS(i,j-1),if x,i,= y,j,then,LCS(i,j) = 1 + LCS(i-1,j-1),Running time = O(mn),10,Optimal matrix multiplication,a,b,b,c,=,A = a x b matrix,B = b x c matrix,How many operations to compute AB ?,11,Optimal matrix multiplication,a,b,b,c,=,12,Optimal matrix multiplication,a,b,b,c,=,each entry of A * B takes,(b) time,need to compute ac entries,(abc) time,total,13,Optimal matrix multiplication,N x N,matrix,N x N,matrix,A,B,Compute AB, time = ?,14,Optimal matrix multiplication,N x N,matrix,N x N,matrix,A,B,Compute AB, time =,(N,3,),15,Optimal matrix multiplication,N x N,matrix,N x N,matrix,A,B,Compute AB, time =,(N,3,),Compute ABC, time = ?,C,N x 1 matrix,16,Optimal matrix multiplication,N x N,matrix,N x N,matrix,A,B,Compute D=BC, time = ?,Compute AD, time = ?,Compute ABC, time = ?,C,N x 1 matrix,17,Optimal matrix multiplication,N x N,matrix,N x N,matrix,A,B,Compute D=BC, time =,(N,2,),Compute AD, time = ?,Compute ABC, time = ?,C,N x 1 matrix,18,Optimal matrix multiplication,N x N,matrix,A,Compute D=BC, time =,(N,2,),Compute AD, time = ?,Compute ABC, time = ?,D,N x 1 matrix,19,Optimal matrix multiplication,N x N,matrix,A,Compute D=BC, time =,(N,2,),Compute AD, time =,(N,2,),Compute ABC, time =,(N,2,),D,N x 1 matrix,20,Optimal matrix multiplication,N x N,matrix,N x N,matrix,A,B,(AB)C = ABC = A(BC),C,N x 1 matrix,The order of evaluation,does not change the result,can change the amount of work needed,21,Optimal matrix multiplication,a,1,a,2,a,3,.,a,n,n-1 matrices of sizes,a,1,x a,2,B,1,a,2,x a,3,B,2,a,3,x a,4,B,3,.,a,n-1,x a,n,B,n-1,What order should we multiply them in?,22,Optimal matrix multiplication,B,1,B,2,B,3,B,4, B,n-1,B,1,(B,2,B,3,B,4, B,n-1,),(B,1,B,2,) (B,3,B,4, B,n-1,),(B,1,B,2,B,3,) (B,4, B,n-1,),(B,1,B,2,B,3,B,4,) B,n-1,23,Optimal matrix multiplication,B,1,B,2,B,3,B,4, B,n-1,Ki,j = the minimal number of operations,needed to multiply B,i, B,j,B,i,(B,i+1,B,i+2, B,j,),(B,i,B,i+1,) (B,i+2, B,j,),(B,i,B,i+1,B,i+2,) ( B,j,),(B,1,B,2,B,3,) B,j,Ki,i + Ki+1,j + a,i,a,i+1,a,j+1,Ki,i+1 + Ki+2,j + a,i,a,i+2,a,j+1,Ki,i+2 + Ki+3,j + a,i,a,i+3,a,j+1,Ki,j-1 + Kj,j + a,i,a,j,a,j+1,24,Optimal matrix multiplication,B,1,B,2,B,3,B,4, B,n-1,Ki,j = the minimal number of operations,needed to multiply B,i, B,j,Ki,j = min Ki,w + Kw+1,j + a,i,a,w+1,a,j,i,w2 then,KS,u,v = min KS-u,w,v + d(u,w),w,S-u,v,32,Travelling Salesman Problem,if S=u,v then KS,u,v=d(u,v),if |S|2 then,KS,u,v = min KS-u,w,v + d(u,w),w,S-u,v,Running time = ?,K,2,n,n,2,33,Travelling Salesman Problem,if S=u,v then KS,u,v=d(u,v),if |S|2 then,KS,u,v = min KS-u,w,v + d(u,w),w,S-u,v,Running time = O(n,3,2,n,),K,2,n,n,2,34,Travelling Salesman Problem,dynamic programming = O(n,3,2,n,),brute force = O(n!),35,Longest increasing subsequence,INPUT: numbers a,1, a,2, . , a,n,OUTPUT: longest increasing subsequence,1,9,2,4,7,5,6,1,9,2,4,7,5,6,36,Longest increasing subsequence,INPUT: numbers a,1, a,2, . , a,n,OUTPUT: longest increasing subsequence,reduce to a problem that we saw today,37,Longest increasing subsequence,INPUT: numbers a,1, a,2, . , a,n,OUTPUT: longest increasing subsequence,38,Longest increasing subsequence,INPUT: numbers a,1, a,2, . , a,n,OUTPUT: longest increasing subsequence,Ki,j = the minimum last element of an,increasing seqence in a,1, . ,a,i,of length j (if no sequence, ,),K0.n,0.n,39,Longest increasing subsequence,Ki,j = the minimum last element of an,increasing seqence in a,1, . ,a,i,of length j (if no sequence, ,),K0.n,0.n,true/false: Ki,j,Ki,j+1 ?,40,Longest increasing subsequence,Ki,j = the minimum last element of an,increasing seqence in a,1, . ,a,i,of length j (if no sequence, ,),K0.n,0.n,K0,j = ? for j,1,K0,0 = ?,41,Longest increasing subsequence,Ki,j = the minimum last element of an,increasing seqence in a,1, . ,a,i,of length j (if no sequence, ,),K0.n,0.n,K0,j =,for j,1,K0,0 = -,42,Longest increasing subsequence,Ki,j = the minimum last element of an,increasing seqence in a,1, . ,a,i,of length j (if no sequence, ,),K0.n,0.n,Ki,j = ?,43,Longest increasing subsequence,Ki,j = the minimum last element of an,increasing seqence in a,1, . ,a,i,of length j (if no sequence, ,),K0.n,0.n,Ki,j = a,i,if a,i, Ki-1,j-1,Ki,j = Ki-1,j otherwise,44,Longest increasing subsequence,Ki,j = the minimum last element of an,increasing seqence in a,1, . ,a,i,of length j (if no sequence, ,),K0.n,0.n,Ki,0 = -,Ki,1 =,Ki,2 =,.,Ki,j =,Ki,j+1 =,a,i, Ki-1,j-1,45,Longest increasing subsequence,K0,0 = -,K0,1 =,K0,2 =,K0,3 =,K0,4 =,K0,5 =,K0,6 =,1,9,2,4,7,5,6,46,Longest increasing subsequence,K1,0 = -,K1,1 = 1,K1,2 =,K1,3 =,K1,4 =,K1,5 =,K1,6 =,1,9,2,4,7,5,6,47,Longest increasing subsequence,K1,0 = -,K1,1 = 1,K1,2 =,K1,3 =,K1,4 =,K1,5 =,K1,6 =,1,9,2,4,7,5,6,48,Longest increasing subsequence,K2,0 = -,K2,1 = 1,K2,2 = 9,K2,3 =,K2,4 =,K2,5 =,K2,6 =,1,9,2,4,7,5,6,49,Longest increasing subsequence,K2,0 = -,K2,1 = 1,K2,2 = 9,K2,3 =,K2,4 =,K2,5 =,K2,6 =,1,9,2,4,7,5,6,50,Longest increasing subsequence,K3,0 = -,K3,1 = 1,K3,2 = 2,K3,3 =,K3,4 =,K3,5 =,K3,6 =,1,9,2,4,7,5,6,51,Longest increasing subsequence,K3,0 = -,K3,1 = 1,K3,2 = 2,K3,3 =,K3,4 =,K3,5 =,K3,6 =,1,9,2,4,7,5,6,52,Longest increasing subsequence,K4,0 = -,K4,1 = 1,K4,2 = 2,K4,3 = 4,K4,4 =,K4,5 =,K4,6 =,1,9,2,4,7,5,6,53,Longest increasing subsequence,K4,0 = -,K4,1 = 1,K4,2 = 2,K4,3 = 4,K4,4 =,K4,5 =,K4,6 =,1,9,2,4,7,5,6,54,Longest increasing subsequence,K5,0 = -,K5,1 = 1,K5,2 = 2,K5,3 = 4,K5,4 = 7,K5,5 =,K5,6 =,1,9,2,4,7,5,6,55,Longest increasing subsequence,K5,0 = -,K5,1 = 1,K5,2 = 2,K5,3 = 4,K5,4 = 7,K5,5 =,K5,6 =,1,9,2,4,7,5,6,56,Longest increasing subsequence,K6,0 = -,K6,1 = 1,K6,2 = 2,K6,3 = 4,K6,4 = 5,K6,5 =,K6,6 =,1,9,2,4,7,5,6,57,Longest increasing subsequence,K6,0 = -,K6,1 = 1,K6,2 = 2,K6,3 = 4,K6,4 = 5,K6,5 =,K6,6 =,1,9,2,4,7,5,6,58,Longest increasing subsequence,K7,0 = -,K7,1 = 1,K7,2 = 2,K7,3 = 4,K7,4 = 5,K7,5 = 6,K7,6 =,1,9,2,4,7,5,6,answer = 5,59,