Number of major successes fields Related aspect a Number theoretic algorithms-these a Abstract model of computer: algorithms make it possible to implement a High level of languanges cryptosystems such as the RSA public key cryptosystem ion algorithms-these algorithms allow us to transmit data more efficiently over for example phone lines a Geometric algorithms- displaying images quickly on a screen often makes use of nIques Divide and conquer Example of a divide and conquer a Divide and Conquer is a method Problem: sorting{12,3455,21,7,9,1,10} m Applying cases a Divide: it is too big to solve if it is smaller we A large size problem, how to solve it may solve it, so we divide it into two problem We can solve small size problems a Sub-problem1: sorting( 12, 3, 45, 5, 211 Divide it into several small size problems Solve these small size sub-problems a Sub-problem2: sorting(7, 9, 1, 101 a Next, what shall we do? the original problem 1. Merge(A, B)lIA and B are two sorted Arrays C lito store the result =0∥ index of o I Conquer: we use some methods(any kind of While not end of A and B /r<A length& S<Blength to solve it and get the sub-problems'solutions If(Ar]<B(s) then that means we sort the two sub-problems Solution of sub-problem 1: (3, 5, 12, 21, 45) a Solution of 1,7,9,10} we should use these two solutions Append B(s,., B length-1]to C see next page Append A(r, -. Alength-1]to C6 清华大学 宋斌恒 31 Number of major successes fields n Number theoretic algorithms - these algorithms make it possible to implement cryptosystems such as the RSA public key cryptosystem. n Compression algorithms - these algorithms allow us to transmit data more efficiently over, for example, phone lines. n Geometric algorithms - displaying images quickly on a screen often makes use of sophisticated algorithmic techniques. 清华大学 宋斌恒 32 Related aspect n Abstract model of computer: n High level of languanges 清华大学 宋斌恒 33 Divide and Conquer n Divide and Conquer is a method n Applying cases: n A large size problem, how to solve it? n We can solve small size problems! n Divide it into several small size problems, n Solve these small size sub-problems! n Next, what shall we do? n Combine the sub-solution to get the solution of the original problem. 清华大学 宋斌恒 34 Example of a Divide and Conquer n Problem: sorting {12,3,45,5,21,7,9,1,10} n Divide: it is too big to solve, if it is smaller we may solve it, so we divide it into two problem: n Sub-problem1: sorting{12,3,45,5,21} n Sub-problem2: sorting{7,9,1,10} 清华大学 宋斌恒 35 n Conquer: we use some methods (any kind of) to solve it and get the sub-problems’solutions, that means we sort the two sub-problems: n Solution of sub-problem1:{3,5,12,21,45} n Solution of sub-problem2:{1,7,9,10} n Combine: we should use these two solutions to construct the solution of the original problem, see next page 清华大学 宋斌恒 36 1. Merge(A, B) //A and B are two sorted Arrays 1. r=s=0; 2. Create array C //to store the result 3. i=0 //index of C 4. While not end of A and B //r<A.length & s<B.length 1. If(A[r]<B[s]) then 1. C[i]=A[r]; 2. r++; i++; 2. Else 1. C[i]=B[s]; 2. s++; i++; 5. If(r==A.length) 1. Append B[s,… ,B.length-1] to C 6. Else 1. Append A[r,… ,A.length-1] to C 7. Return C