Transform and Conquer (I),Chapter 6,Introduction to Transform-and-Conquer Its Application to Numerical Problem Linear Equation Calculating Polynomials,2019/6/21,3,2012-2013-01 Design and Analysis of Algorithm SCUN,Goals of the Lecture,At the end of this lecture, you should Master the basic idea and all kinds of variations of transform and conquer technique Master the linear equation solving algorithm and its analysis Master the Polynomials calculating algorithm and its analysis,2019/6/21,4,2012-2013-01 Design and Analysis of Algorithm SCUN,Transform and Conquer (basic idea),Second, the modified instance is solved, we call this as a conquering stage,Original instance,More amenable instance,Solution,transform,conquer,Transform and conquer deals with a group of design methods that are based on the idea of transformation,First, the original problems instance is modified to be more amenable to solve, we call this as a transformation stage,2019/6/21,5,2012-2013-01 Design and Analysis of Algorithm SCUN,3 Types of Transform and Conquer,Computing the least common multiple Linear programming,Instance simplification: Transform to a simpler/more convenient instance of the same problem,Presorting Solving linear equation,Representation change: Transform to a different representation of the same instance,Calculating polynomial Heap sort,Problem reduction: Transform to a different problem for which an algorithm is already available,2019/6/21,6,2012-2013-01 Design and Analysis of Algorithm SCUN,Instance simplification - Presorting,Also: Presorting is used in many geometric algorithms.,Many problems involving lists are easier when list is sorted.,searching,computing a mode,checking if all elements are distinct (element uniqueness),a value that occurs most often in a given list of numbers,2012-2013-01 Design and Analysis of Algorithm SCUN,Instance simplification: Linear equation Examples and General form(p203-208),Standard method (cramer method),Example: How to solve the problem of chickens and rabbits in the same cage?,Generally, a system of linear equations is a set of n equations with n unknown variables. Typically these equations can be written as: a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 . an1x1 + an2x2 + + annxn = bn,2012-2013-01 Design and Analysis of Algorithm SCUN,Instance simplification: Linear equation Gauss Method,Solve the latter by substitutions starting with the last equation and moving up to the first one (Backward substitution),Transform to: An equivalent system of n linear equations in n unknowns with an upper triangular coefficient matrix (Elimination),2012-2013-01 Design and Analysis of Algorithm SCUN,Instance simplification: Linear equation Elimination process,So the result would be:,From the first row to last row (k=1,2,n), we do the following transform (elementary operations):,2012-2013-01 Design and Analysis of Algorithm SCUN,Instance simplification: Linear equation Backward substitution process,So the result would be:,From the last row to the first row (i=n,n-1,1), we can do the following backward substitution:,2012-2013-01 Design and Analysis of Algorithm SCUN,Example of Gauss method,Result: x1= 2, x2 = 1, x3 = 6,Solve 2x1 - 4x2 + x3 = 6 3x1 - x2 + x3 = 11 x1 + x2 - x3 = -3,2012-2013-01 Design and Analysis of Algorithm SCUN,Algorithm Description,void GSElimination(int n, double *a, double *b) int k, i, j; for(k=0; kn; k+) /Elimination process for(j=k+1; jn; j+) akj = akj/akk; bk = bk/akk; for(i=k+1; in; i+) for(j=k+1; jn; j+) aij = aij - aik*akj; bi = bi - aik*bk; ,2012-2013-01 Design and Analysis of Algorithm SCUN,Algorithm Description (cont.),/Backward substitution process for(i=n-2; i=0; i-) for(j=i+1; jn; j+) bi = bi - aij*bj; / end of algorithm,2019/6/21,14,2012-2013-01 Design and Analysis of Algorithm SCUN,Algorithm analysis,So the total numbers of multiplications is:,The elimination process,The backward substitution process,2019/6/21,15,2012-2013-01 Design and Analysis of Algorithm SCUN,Thinking,Is the algorithm described before always correct?,No. If Ai,i=0, we can not divide by it and hence cannot use the ith row as a pivot for the ith iteration of the algorithm,How to fix the above problem?,We can use the first elementary transformation to exchange the ith row with some row below it that has a nonzero coefficient in the ith column.,Has any other problem?,Yes. If Ai,i is so small and consequently the scaling factor Aj,i/Ai,i so large that the new value of Aj,k might become distorted by a round-off error.,How to fix the above problem?,Always look for a row with the largest absolute value of coefficient in the ith column and exchange it with the ith row,16,2012-2013-01 Design and Analysis of Algorithm SCUN,Representation Change Polynomial Evaluat