1、2023-5-122010-2011-01 Design and Analysis of Algorithm SCUECReview of last classbThe difference between quick sort and merge sort Divide step Combine step Stable or not In place or not Time efficiencybQuick sort algorithmDivide and Conquer(III)Chapter 4l Application to numerical problemn Large integ
2、ers multiplicationn Matrices multiplicationl Application to combinatorial problemn Tromino puzzle2023-5-142010-2011-01 Design and Analysis of Algorithm SCUECGoals of the LecturebAt the end of this lecture,you should Understand the algorithm based on DAC for solving large integers multiplication and
3、its analysis Master the Strassens matrix multiplication algorithm and its analysis2023-5-152010-2011-01 Design and Analysis of Algorithm SCUECMultiplication of Large Integers The grade-school algorithm:a1 a2 an b1 b2 bn (d10)d11d12 d1n (d20)d21d22 d2n (dn0)dn1dn2 dnnConsider the problem of multiplyi
4、ng two(large)n-digit integers represented by arrays of their digits such as:A=12345678901357986429 B=87654321284820912836Efficiency:n2 one-digit multiplications.too inefficient!2023-5-162010-2011-01 Design and Analysis of Algorithm SCUECStandard Algorithm based on DACA=B=Where:A=A1*10n/2+A2 B=B1*10n
5、/2+B2 A B=A1 B110n+(A1 B2+A2 B1)10n/2+A2 B2A1B1B2A2bSuppose the n-digits of the two integers is a power of 2,i.e.n=2k,then we can divide them as follows:b Efficiency:T(n)=4T(n/2),T(1)=1 Solution:T(n)=n2 bA small example:A=2135 and B=4014 no improvement!2023-5-172010-2011-01 Design and Analysis of Al
6、gorithm SCUECImproved Algorithm based on DACbIn order to improve the time complexity,the numbers of multiplication must be decreased.bTwo solutions:A B=A1 B110n+(A1+A2)*(B1+B2)-A1 B1-A2 B2)10n/2+A2 B2 A B=A1 B110n+(A1-A2)*(B2 B1)+A1 B1+A2 B2)10n/2+A2 B2b Efficiency:T(n)=3T(n/2),T(1)=1 Solution:T(n)=
7、nlog3 bigger improvement!A B=A1 B110n+(A1 B2+A2 B1)10n/2+A2 B22023-5-182010-2011-01 Design and Analysis of Algorithm SCUECvoid MATRIX_MULTIPLY(float An,float Bn,float Cn)for(int i=0;in;i+)for(int j=0;jn;j+)Cii=Ai0*B0j;for(k=1;k=2 T(1)=1bIn fact,the recursive version requires n3 multiplications and n
8、3 n2 additions,so it is not more efficient than the standard one.On the contrary,it is cost more in terms of both time and space brought by recursion.bT(n)=n3+(n3-n2)2023-5-1122010-2011-01 Design and Analysis of Algorithm SCUECStrassens Matrix MutiplicationbUses a set of seven formulas to multiply t
9、wo 22 matricesbThe formulas do not rely on elements being commutative under multiplication,so the elements can be matrices bIt can be applied recursively,in other words,two 4 4 matrices can be multiplied by treating each as a 2 2 matrix of 2 2 matrices2023-5-1132010-2011-01 Design and Analysis of Al
10、gorithm SCUECStrassens Formulas(I)bFirst we calculate a set of temporary values:m1=(A1,1+A2,2)*(B1,1+B2,2)m2=(A2,1+A2,2)*B1,1m3=A1,1*(B1,2-B2,2)m4=A2,2*(B2,1-B1,1)m5=(A1,1+A1,2)*B2,2m6=(A2,1-A1,1)*(B1,1+B1,2)m7=(A1,2-A2,2)*(B2,1+B2,2)111211121112212221222122,=AABBCCAHCAABBCC2023-5-1142010-2011-01 De
11、sign and Analysis of Algorithm SCUECStrassens Formulas(II)bCan you write out the strassens algorithm?(description)1111122111121222111221112221211222222122A BA BA BA BCCCA BA BA BA BCCbThe result is then calculated by:C1,1=m1+m4-m5+m7 C2,1=m2+m4C1,2=m3+m5C2,2=m1+m3-m2+m62023-5-1152010-2011-01 Design
12、and Analysis of Algorithm SCUECAlgorithm analysisbThese formulas require 7 multiplications and 18 additions to multiply two 2 2 matricesbThe real savings occur when this is applied recursively and we do approximately n2.81 multiplications and 6n2.81-6n2 additionsbThough not used in practice,Strassen
13、s method is important because it was the first algorithm that is faster than O(n3)T(n)=7T(n/2)+18(n/2)2 if n=2 T(1)=1 T(n)=nlog7+6nlog7 6n22023-5-1162010-2011-01 Design and Analysis of Algorithm SCUECStandard vs DAC vs Strassen6n2.81-6n2n2.81Strassens algorithmn3Standard algorithm based on DACn3-n2n
14、3Standard algorithmAdditionsMultiplicationsn3-n2DACs Application to Combinatorial Problemn Tromino puzzle2023-5-1182010-2011-01 Design and Analysis of Algorithm SCUECbProblem description A tromino is an L-shaped tile formed by three adjacent squares of a chess board.The problem is to cover any 2k2k
15、chessboard with one missing square(any where on the board)with trominos.Trominos should cover all the squares except the missing one with no overlaps.Tromino Puzzle(Chess board cover)2023-5-1192010-2011-01 Design and Analysis of Algorithm SCUECAlgorithm Based on Divide and Conquer TechniquebIdea Div
16、ide the 2k2k grid into four 2k-12k-1 subgrids(see figure(a).Suppose the missing square is in the NW subgrid.Remove the squares closest to the center of the grid from the other three subgrids.The three removed squares in the NE,SW,SE subgrids can be tiled with a single triomino(see figure(b).2023-5-1
17、202010-2011-01 Design and Analysis of Algorithm SCUECAlgorithm analysisbLet T(k)denotes the time needed to cover any 2k2k chessboard,From the dividing strategy,we can get the time recurrence relation as follows:bThe above recurrence relation works out to:bThe triomino tiles needed to cover any 2k2k
18、chessboard are(4k-1)/3.So the algorithm is optimal(1)0()4(1)(1)0OkT kT kOk()(4)kT kOThe End2023-5-1222010-2011-01 Design and Analysis of Algorithm SCUECAssignmentsbReading assignment:Textbook page 149-154bExercise:No 2,6,7 of exercises 4.5(p148)2023-5-1232010-2011-01 Design and Analysis of Algorithm
19、 SCUECStrassens algorithm(I)void STRASSEN(int n,float An,float Bn,float Cn)float A11nn,A12nn,A21nn,A22nn;float B11nn,B12nn,B21nn,B22nn;float C11nn,C12nn,C21nn,C22nn;float m1nn,m2nn,m3nn,m4nn,m5nn,m6nn,m7nn;float AAnn,BBnn,MM1nn,MM2nn;int i,j;if(n=2)/multiplied by standard algorithm directly MATRIX_M
20、ULTIPLY(A,B,C);2023-5-1242010-2011-01 Design and Analysis of Algorithm SCUECelse /(1)divide matrix A and B into four blocks for(i=0;in/2;i+)for(j=0;jn/2;j+)A11ij=Aij;A12ij=Aij+n/2;A21ij=Ai+n/2j;A22ij=Ai+n/2j+n/2;B11ij=Bij;B12ij=Bij+n/2;B21ij=Bi+n/2j;B22ij=Bi+n/2j+n/2;Strassens algorithm(II)/(2)calcu
21、late m1,m2,.,m7 recursively MATRIX_ADD(n/2,A11,A22,AA);MATRIX_ADD(n/2,B11,B22,BB);STRASSEN(n/2,AA,BB,m1);/m1=(A11+A22)*(B11+B22)MATRIX_ADD(n/2,A21,A22,AA);STRASSEN(n/2,AA,B11,m2);/m2=(A21+A22)*B11 MATRIX_SUB(n/2,B12,B22,BB);STRASSEN(n/2,A11,BB,m3);/m3=A11*(B12-B22)MATRIX_SUB(n/2,B21,B11,BB);STRASSEN
22、(n/2,A22,BB,m4);/m4=A22*(B21-B11)MATRIX_ADD(n/2,A11,A12,AA);STRASSEN(n/2,AA,B22,m5);/m5=(A11+A12)*B22 MATRIX_SUB(n/2,A21,A11,AA);MATRIX_ADD(n/2,B11,B12,BB);STRASSEN(n/2,AA,BB,m6);/m6=(A21-A11)*(B11+B12)MATRIX_SUB(n/2,A12,A22,AA);MATRIX_ADD(n/2,B21,B22,BB);STRASSEN(n/2,AA,BB,m7);/m7=(A12-A22)*(B21+B2
23、2)/(3)calculate C11,C12,C21,C22 MATRIX_ADD(n/2,m1,m4,MM1);MATRIX_SUB(n/2,m5,m7,MM2);MATRIX_SUB(n/2,MM1,MM2,C11);/C11=m1+m4-m5+m7 MATRIX_ADD(n/2,m3,m5,C12);/C12=m3+m5 MATRIX_ADD(n/2,m2,m4,C21);/C21=m2+m4 MATRIX_ADD(n/2,m1,m3,MM1);MATRIX_SUB(n/2,m2,m6,MM2);MATRIX_SUB(n/2,MM1,MM2,C22);/C22=m1+m3-m2+m6
24、/(4)combine C11,C12,C21,C22 into C for(i=0;in/2;i+)for(j=0;jn/2;j+)Cij=C11ij;Cij+n/2=C12ij;Ci+n/2j=C21ij;Ci+n/2j+n/2=C22ij;/else finishedvoid chessBoard(int tr,int tc,int dr,int dc,int size)if(size=1)return;int t=tile+;/number of L-shaped tile s=size/2;/partition chess board /cover the left-top sub
25、chess board if(dr tr+s&dc tc+s)/missing square in this sub chess board chessBoard(tr,tc,dr,dc,s);/handle it recursively else /cover the right-down square with t L-shaped tile boardtr+s-1tc+s-1=t;chessBoard(tr,tc,tr+s-1,tc+s-1,s);/cover the right-top sub chess board if(dr=tc+s)/missing square in this
26、 sub chess board chessBoard(tr,tc+s,dr,dc,s);else /cover the left-down square with t L-shaped tile boardtr+s-1tc+s=t;chessBoard(tr,tc+s,tr+s-1,tc+s,s);Chess Board Cover Algorithm(I)2023-5-1282010-2011-01 Design and Analysis of Algorithm SCUEC /cover the left-down chess board if(dr=tr+s&dc=tr+s&dc=tc+s)/missing square in this sub chess board chessBoard(tr+s,tc+s,dr,dc,s);else /cover the left-top square with t L-shaped tile boardtr+stc+s=t;chessBoard(tr+s,tc+s,tr+s,tc+s,s);Chess Board Cover Algorithm(II)
