Analysis Of Algorithms
Analysis Of Algorithms CS 3343
Popular in Course
Popular in ComputerScienence
verified elite notetaker
This 6 page Class Notes was uploaded by Mireya Heidenreich on Thursday October 29, 2015. The Class Notes belongs to CS 3343 at University of Texas at San Antonio taught by Staff in Fall. Since its upload, it has received 11 views. For similar materials see /class/231393/cs-3343-university-of-texas-at-san-antonio in ComputerScienence at University of Texas at San Antonio.
Reviews for Analysis Of Algorithms
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/29/15
Chapter 6 Transform and Conquer You can never solve a problem on the level on which it was cre ated Albert Einstein We cannot solve our problems with the same thinking we used when we created them Albert Einstein Introduction 2 Presorting Example 3 Gaussian Elimination 4 System of Linear Equations 4 Example of Linear Equations 5 Forward Elimination 6 Forward Elimination Algorithm 7 Backward Substitution 8 Backward Substitution Algorithm 9 Comments on Gaussian Elimination 10 Balanced Search Trees AVL Trees 11 Binary Search Tree Notation 11 AVL Trees 12 Binary Search Tree Insertion 13 RRotation 14 LRRotation 15 Balancing AVL Trees 16 AVL Illustration 17 Analysis of AVL Trees 18 Homer s Rule and Fast Exponentiation Horner s Algorithm Fast Exponentiation Fast Exponentiation Algorithm 22 Introduction Gaussian Elimination Transformand conquer is an approach to solving a problem by changing an System of Linear Equations instance to Gaussian Elimination is an algorithm solving a system of n linear equations in n D a snmpler Instance of the same problem or unknowns D a different representation of the same problem or D an instance of a different problem 11331 12331 a1nn 51 2111 l 2211 l l agnl n 2 b2 simpler instance or problem39s another representation solution Instance or anlml an21 o o o annmn bn another problem39s instance FIGURE61 T f d ransorman conquersmegy where CW and by are the coeffICIents and xj are the unknowns CS 3343 Analysis of Algorithms Chapter 6 Slide 2 For example the linear least squares method in statistics needs to solve this kind Presorting Example of system CS 3343 Analysis of Algorithms Chapter 6 Slide 4 Presorting sorting the data in advance makes it easier to D Check element uniqueness Example of Linear Equations D Compute the mode 5 Search the data For example consider this system of 3 equations E Find the minimum maximum median or an order statistic y 21 2334 3122 326 CS 3343 Analysis of Algorithms Chapter 6 Slide 3 51l 2 2323 This system has the solution x1 54 232 134 and 233 134 Gaussian elimination works in two stages forward elimination and backward substitution Forward elimination addssubtracts equations from each other CS 3343 Analysis of Algorithms Chapter 6 Slide 5 Forward Elimination Backward Substitution 2 1 3 4 Solving last equation 4x3 13 yields x3 134 3 2 16 row2732row1 75 1 72 3 row 3 52 row 1 Substitute for 963 in second equation 72962 7 72963 0 7 2x2 0 72353 0918 918 952 91872 134 Substitute for 962 and 963 in first equation 2 7 3 0 72 772 0 0 732 112 13 row337 row2 2 71 3 4 0 72 772 0 2x17x23x34 0 0 413 2x14x273x3413431134 29617104 Chaptar Slld275 x1 754 cs 3343 Analyse ofAlgorlthms cs 3343 Analyse ofAlgorlthms Chapter 5 snag a s Forward Elimination Algorithm Backward Substitution Algorithm algorithm ForwardElz39mA1un1ttnb1 n First stage to solve Ax b by Gaussi n Elim Input A matrix A and column b a39g739s l 3nfiifgiaiiiiliiill i llsyn illnn Elm Output Equivalent uppertriangular matrix I A I A for i H 1 n do nput n uppertrlangu ar matrlx A 1 b Output Solutlon columnvector x for ll n it E lllldo for i lt7 n downto 1 do 1 lt7 n 7 s lt7 A1n 1 gut121 row130 d5 SHS AiJHij 111147 51111017 AM 5 filmAll 1 xli e sAi i return at cs 3343 Analyse ofAlgorlthms Chapter 5 snag a 7 Chapter 5 snag a g cs 3343 Analyse ofAlgorlthms Comments on Gaussian Elimination D D D CS 3343 Analysis of Algorithms Gaussian Elimination requires that A be nonsingular See your linear algebra book Gaussian Elimination is n3 Note triple loop in ForwardEim Better numerical properties can be obtained through partial pivoting See book LU decomposition is an extension of Gaussian elimination After n3 preprocessing of the A matrix only n2 is needed for any 9 vector See book Similar processing can be used to compute matrix inverse and determinant Chapter 6 Slide 10 AVL Trees D For each node in binary search tree all keys on its left are S to its key and all keys on its right are 2 to its key D In a balanced search tree the height is log where n is the number of nodes D For each node in an AVL tree the heights of the left and right subtree are equal or differ by one D The balance factor is the left height minus the right height D Tree rotations are used to transform the tree into balance CS 3343 Analysis of Algorithms Chapter 6 Slide 12 Balanced Search Trees AVL Trees 11 SUBBED CS 3343 Analysis of Algorithms Binary Search Tree Notation Txmot is the root of tree T or null azkey is the key of node x 3par6nt is the parent of x or null 3left is the left child of x or null 3rz39ght is the right child of x or null 3hez39ght is the height of x nullhez39ght 1 Chapter 6 Slide 11 Binary Search Tree Insertion algorithm TreensertT Z Inserts a node into a binary search tree Input Tree T and node 2 y 9 null x 9 Txroot while x null do y 9 a if zkey lt azkey then x 9 13 left else x 9 alright 2parent 9 y if y null then Tr00t 9 2 else if zkey lt yk6y then yieft 9 2 else yright 9 2 CS 3343 Analysis of Algorithms Chapter 6 Slide 13 RRotation Balancing AVL Trees An R rotation is used when the left child is too high and the left left grandchild is as high or higher than the left right one algorithm AVLBalam lt97gt single R rotation CI 0 o Output 1 and nodes above it are balanced 0 while 1 null do A gt A if 1lefthez39ght gt 5137 z39ghthez39ght 1 then A A T2 T3 if 13 left lefthez ght lt 13 left m ghthez ght then LRRotatt0na FIGURE 64 General form of the Rrotation in the AVL tree A shaded node is the last One 39 s frted39 else if 13 left height 1 lt 13 right height then CS 3343 Anay5is of Algorithms Chapter 6 Slide 14 if 13 right lefthez ght gt 5137 z39ghtm39ghthez39ght then RLRotatt0na LRRotation else LRotatz on v a F 3parent An LR rotation is used when the left child is too high and the left right grandchild is higher than the left left one double LR rotation CS 3343 Analysis of Algorithms Chapter 6 Slide 16 OAII 1 quotInqz39l39ra39l39inn a e 4 us 9 6 6 9 O 9 39 2 1 0 2 0 35 0 O O a e 1 e e gt 0 e 0 9 FIGURE 65 General form of the double LRrotation in the AVL tree A shaded node a 9 9 a is the last one inserted It can be either in the left subtree or in the right 0 subtree of the root s grandchild 9 CS 3343 Analysis of Algorithms Chapter 6 Slide 15 CS 3343 Analysis of Algorithms Chapter 6 Slide 17 Analysis of AVL Trees The height h of an AVL tree with n nodes satisfies log2n2 lt h lt 1510an D A binary tree of height h has g 2111171 nodes n lt 2th1 7gt n2 lt 211 7gt log2n2 lt h D An AVL tree with height h at worst has subtrees of height h 71 and h 7 2 D Assuming heights h 71 and h 7 2 have at least 161 and 16 2 nodes respectively n gt 16 1 14r1t6h 2 gt16h e 1611 lt n 7gt h lt1510g2n CS 3343 Anzlysls ofAlgorlthms Chapter 5 Sllda e 18 Homer39s Rule and Fast Exponentiation Horner s Rule Horner s rule is an efficient algorithm for evaluating a polynomial For example D 5962 7 396 8 can be evaluated by 596 3x 8 D 7963 962 7 9x 7 2 can be evaluated by 796 1x 7 9x 7 2 The generalization of this is Horner s rule It performs n multiplications and n additionssubtractions for an n degree polynomial CS 3343 Anzlysls ofAlgorlthms Chapter 5 Sllda e 19 Horner s Algorithm algorithm Home PlOn x Evaluates a polynomial at x lnput A value x and an array P of coefficients Output The value of the polynomial at x v lt7 PM for i lt7 n71downt00 do 1 lt7 x as v return 1 CS 3343 Anzlysls ofAlgorlthms Chapter 5 Sllda e 20 Fast Exponentiation We can evaluate xquot quickly based on the binary expansion of the exponent For example D 210 can be evaluated by 210 210102 28 as 22 D 213 can be evaluated by 213 211012 28 as 24 as 2 D Algorithm on next page corresponds to books right to left algorithm CS 3343 Anzlysls ofAlgorlthms Chapter 5 Sllda e 21