Question? Leave a message!




Divide-and-conquer algorithms

Divide-and-conquer algorithms
ECE 250 Algorithms and Data Structures Divideand conquer Douglas Wilhelm Harder, M.Math. LEL algorithms Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Divideandconquer algorithms 2 Divideandconquer algorithms We have seen four divideandconquer algorithms: – Binary search – Depthfirst tree traversals – Merge sort – Quick sort The steps are: – A larger problem is broken up into smaller problems – The smaller problems are recursively – The results are combined together again into a solutionDivideandconquer algorithms 3 Divideandconquer algorithms For example, merge sort: – Divide a list of size n into b = 2 sublists of size n/2 entries – Each sublist is sorted recursively – The two sorted lists are merged into a single sorted listDivideandconquer algorithms 4 Divideandconquer algorithms More formally, we will consider only those algorithms which: – Divide a problem into b subproblems, each approximately of size n/b • Up to now, b = 2 – Solve a ≥ 1 of those subproblems recursively • Merge sort and tree traversals solved a = 2 of them • Binary search solves a = 1 of them – Combine the solutions to the subproblems to get a solution to the overall problemDivideandconquer algorithms 5 Divideandconquer algorithms With the three problems we have already looked at we have looked at two possible cases for b = 2: Merge sort b = 2 a = 2 Depthfirst traversal b = 2 a = 2 Binary search b = 2 a = 1 Problem: the first two have different run times: Merge sortQ(n ln(n) ) Depthfirst traversalQ(n)Divideandconquer algorithms 6 Divideandconquer algorithms Thus, just using a divideandconquer algorithm does not solely determine the run time We must also consider – The effort required to divide the problem into two subproblems – The effort required to combine the two solutions to the subproblemsDivideandconquer algorithms 7 Divideandconquer algorithms For merge sort: – Division is quick (find the middle): Q(1) – Merging the two sorted lists into a single list is a Q(n) problem For a depthfirst tree traversal: – Division is also quick: Q(1) – A returnfromfunction is preformed at the end which is Q(1) For quick sort (assuming division into two): – Dividing is slow: Q(n) – Once both subproblems are sorted, we are finished: Q(1)Divideandconquer algorithms 8 Divideandconquer algorithms Thus, we are able to write the expression as follows: – Binary search: 1 n 1   n Q(ln(n))  T(n)  TΘ(1) n 1   2   – Depthfirst traversal: 1 n 1  Q(n)  n  T(n)  2TΘ(1) n 1   2   – Merge/quick sort: Q(n ln(n)) 1 n 1   n  T(n)  2TΘ(n) n 1   2   In general, we will assume the work done combined work is of the k form O(n )Divideandconquer algorithms 9 Divideandconquer algorithms Thus, for a general divideandconquer algorithm which: – Divides the problem into b subproblems – Recursively solves a of those subproblems k – Requires O(n ) work at each step requires has a run time 1 n 1   n  T(n) k  a TOn n 1   b   Note: we assume a problem of size n = 1 is solved...Divideandconquer algorithms 10 Divideandconquer algorithms Before we solve the general case, let us look at some more complex examples: – Searching an ordered matrix – Integer multiplication (Karatsuba algorithm) – Matrix multiplicationDivideandconquer algorithms 11 Searching an ordered matrix Consider an n × n matrix where each row and column is linearly ordered; for example: – How can we determine if 19 is in the matrixDivideandconquer algorithms 12 Searching an ordered matrix Consider the following search for 19: – Search across until a 19 i,j + 1 – Alternate between • Searching down until a 19 i,j • Searching back until a 19 i,j This requires us to check at most 3n entries: O(n)Divideandconquer algorithms 13 Searching an ordered matrix Can we do better than O(n) Logically, no: any number could appear in up to n positions, each of which must be checked – Nevertheless: let’s generalize checking the middle entryDivideandconquer algorithms 14 Searching an ordered matrix 17 19, and therefore, we can only exclude the topleft submatrix:Divideandconquer algorithms 15 Searching an ordered matrix Thus, we must recursively search three of the four submatrices – Each submatrix is approximately n/2 × n/2Divideandconquer algorithms 16 Searching an ordered matrix If the number we are searching for was less than the middle element, e.g., 9, we would have to search three different squaresDivideandconquer algorithms 17 Searching an ordered matrix Thus, the recurrence relation must be 1 n 1   n  T(n)  3TΘ(1) n 1   2   because – T(n) is the time to search a matrix of size n × n – The matrix is divided into 4 submatrices of size n/2 × n/2 – Search 3 of those submatrices – At each step, we only need compare the middle element: Q(1)Divideandconquer algorithms 18 Searching an ordered matrix We can solve the recurrence relationship 1 n 1   n  T(n)  3TΘ(1) n 1   2   using Maple: rsolve( T(n) = 3T(n/2) + 1, T(1) = 1, T(n) ); log (3) 3 2 1 n 2 2 evalf( log2( 3 ) ); 1.584962501Divideandconquer algorithms 19 Searching an ordered matrix 1.585 Therefore, this search is approximately O(n ), which is significantly worse than a linear search:Divideandconquer algorithms 20 Searching an ordered matrix Note that it is T(n) = 3T(n/2) + Q(1) and not T(n) = 3T(n/4) + Q(1) We are breaking the n × n matrix into four (n/2) × (n/2) matrices 2 If N = n , then we could write T(N) = 3T(N/4) + Q(1)Divideandconquer algorithms 21 Searching an ordered matrix Where is such a search necessary – Consider a biparental heap – Without proof, most operations are O( ) including searches n – Binary heaps: most operations are O(ln(n)) but searches are O(n)Divideandconquer algorithms 22 Searching an ordered matrix For example, consider a search for the value 44: nn – The matrix has n entries in See: http://ece.uwaterloo.ca/dwharder/aads/Algorithms/Beaps/Divideandconquer algorithms 23 Searching an ordered matrix Note: the linear searching algorithm is only optimal for square matrices – A binary search would be optimal for a 1 × n or n × 1 matrix – Craig Gidney posts an interesting discussion on such searches when the matrix is not close to square http://twistedoakstudios.com/blog/Post5365searchingasortedmatrixfasterDivideandconquer algorithms 24 Integer multiplication Calculate the product of two 16digit integers 3563474256143563 × 8976558458718976 2 Multiplying two ndigit numbers requires Q(n ) multiplications of two decimal digits: 3563474256143563 × 8976558458718976 21380845536861378 24944319793004941 32071268305292067 28507794049148504 3563474256143563 24944319793004941 28507794049148504 17817371280717815 14253897024574252 n 28507794049148504 17817371280717815 17817371280717815 21380845536861378 24944319793004941 32071268305292067 + 28507794049148504 . 31987734976412811376690928351488Divideandconquer algorithms 25 Integer multiplication Rewrite the product 3563474256143563 × 8976558458718976 as 8 8 (35634742 × 10 + 56143563) × (89765584×10 + 58718976) which requires four multiplications of 8digit integers: 16 (35634742 × 89765584)×10 + 8 (35634742 × 58718976 + 56143563 × 89765584)×10 + (56143563 × 58718976) Adding two ndigit integers is a Q(n) operationDivideandconquer algorithms 26 Integer multiplication Thus, the recurrence relation is: Q (1) n 1   T(n) n   () n 4TQ n1   2   Again, we solve the recurrence relation using Maple: rsolve( T(n) = 4T(n/2) + n, T(1) = 1, T(n) );  n (2n 1) 2 This is still Q(n )Divideandconquer algorithms 27 Integer multiplication To reduce the run time, the Karatsuba algorithm (1961) reduces the number of multiplications Let x = 3563474256143563 y = 8976558458718976 and define x = 35634742 x = 56143563 MS LS y = 89765584 y = 58718976 MS LS and thus 8 x = x ×10 + x MS LS 8 y = y ×10 + y MS LSDivideandconquer algorithms 28 Integer multiplication The multiplication is now: 16 8 xy = x y ×10 + (x y + x y )×10 + x y MS MS L R R L LS LS Rewrite the middle product as x y + x y = (x – x )(y – y ) + x y + x y MS LS LS MS LS MS LS MS MS MS LS LS Two of these are already calculatedDivideandconquer algorithms 29 Integer multiplication Thus, the revised recurrence relation Θ(1) n 1   n T(n)  3TΘ(n) n 1   2   may again be solved using Maple: rsolve( T(n) = 3T(n/2) + n, T(1) = 1, T(n) ); log (3) 2  3n 2n where log (3) ≈ 1.585 2Divideandconquer algorithms 30 Integer multiplication 2 1.585 Plotting the two functions n and n , we see that they are significantly differentDivideandconquer algorithms 31 Integer multiplication This is the same asymptotic behaviour we saw for our alternate searching behaviour of an ordered matrix, however, in this case, it is an improvement on the original run time Even more interesting is that the recurrence relation are different: – T(n) = 3T(n/2) + Q(n) integer multiplication – T(n) = 3T(n/2) + Q(1) searching an ordered matrixDivideandconquer algorithms 32 Integer multiplication In reality, you would probably not use this technique: there are others There are also libraries available for fast integer multiplication For example, the GNU Image Manipulation Program (GIMP) comes with a complete set of tools for fast integer arithmetic http://www.gimp.org/Divideandconquer algorithms 33 Integer multiplication The ToomCook algorithm (1963 and 1966) splits the integers into k 2 parts and reduces the k multiplications to 2k – 1 log (2k – 1) k – Complexity is Q(n ) – Karatsuba is a special case when k = 2 log (5) 1.465 3 – Toom3 (k = 3) results in a run time of Q(n ) = Q(n ) The SchönhageStrassen algorithm runs in Q(n ln(n) ln(ln(n))) time but is only useful for very large integers (greater than 10 000 decimal digits)Divideandconquer algorithms 34 Matrix multiplication Consider multiplying two n × n matrices, C = AB This requires the Q(n) dot product of each of the n rows of A with each of the n columns of B j c i i,j n c a b i, j i,k k, j  k1 3 The run time must be Q(n ) – Can we do betterDivideandconquer algorithms 35 Matrix multiplication In special cases, faster algorithms exist: – If both matrices are diagonal or tridiagonalQ(n) 2 – If one matrix is diagonal or tridiagonalQ(n ) In general, however, this was not believed to be possible to do betterDivideandconquer algorithms 36 Matrix multiplication Consider this product of two n × n matrices – How can we break this down into smaller subproblems Divideandconquer algorithms 37 Matrix multiplication Break each matrix into four (n/2) × (n/2) submatrices – Write each submatrix of C as a sumofproducts A B CDivideandconquer algorithms 38 Matrix multiplication Justification: th th c is the dot product of the i row of A and the j column of B ij c i,jDivideandconquer algorithms 39 Matrix multiplication This is equivalent for each of the submatrices:Divideandconquer algorithms 40 Matrix multiplication We must calculate the four sumsofproducts C = A B + A B 00 00 00 01 10 C = A B + A B 01 00 01 01 11 C = A B + A B 10 10 00 11 10 C = A B + A B 11 10 01 11 11 This totals 8 products of (n/2) × (n/2) matrices 2 – This requires four matrixmatrix additions: Q(n )Divideandconquer algorithms 41 Matrix multiplication The recurrence relation is: Θ(1) n 1   n T(n) 2  8TΘ(n ) n 1   2   Using Maple: rsolve( T(n) = 8T(n/2) + n2, T(1) = 1, T(n) ); 2  n (2n 1)Divideandconquer algorithms 42 Matrix multiplication In 1969, Strassen developed a technique for performing matrix lg(7) 2.807 matrix multiplication in Q(n ) ≈ Q(n ) time – Reduce the number of matrixmatrix productsDivideandconquer algorithms 43 Matrix multiplication Consider the following seven matrix products M = (A –A )(B + B ) 1 00 10 00 01 M = (A + A )(B + B ) 2 00 11 00 11 M = (A –A )(B + B ) 3 01 11 10 11 M = A (B –B ) 4 00 01 11 M = A (B –B ) 5 11 10 00 The four submatrices of C may be written as M = (A + A )B 6 10 11 00 M = (A + A )B 7 00 01 11 C = M + M + M –M 00 3 2 5 7 C = M + M 01 4 7 C = M + M 10 5 6 C = M –M + M –M 11 2 1 4 6Divideandconquer algorithms 44 Matrix multiplication Thus, the new recurrence relation is: Θ(1) n 1   n T(n) 2  7TΘ(n ) n 1   2   Using Maple: rsolve( T(n) = 7T(n/2) + n2, T(1) = 1, T(n) ); 2 log (7) 7 2 4n  n 3 3Divideandconquer algorithms 45 Matrix multiplication Note, however, that there is a lot of additional work required Counting additions and multiplications: 3 2 Classic 2n – n lg(7) 2 Strassen 7n – 6 nDivideandconquer algorithms 46 Matrix multiplication Examining this plot, and then solving explicitly, we find that Strassen’s method only reduces the number of operations for n 654 – Better asymptotic behaviour does not immediately translate into better runtimes The Strassen algorithm is not the fastest 2.376 – the Coppersmith–Winograd algorithm runs in Q(n ) time but the coefficients are too large for any problem Therefore, better asymptotic behaviour does not immediately translate into better runtimesDivideandconquer algorithms 47 Observation lg(n) Some literature lists the runtime as O(7 ) Recall that these are equal: lg(n) lg(7) 7 = n Proof: lg(n) lg(7) lg(n) lg(7) lg(n) lg(n) lg(7) lg(n) lg(7) lg(7) 7 = (2 ) = 2 = 2 = (2 ) = nDivideandconquer algorithms 48 Fast Fourier transform The last example is the fast Fourier transform – This takes a vector from the time domain to the frequency domain The Fourier transform is a linear transform – For finite dimensional vectors, it is a matrixvector product F x n http://xkcd.com/26/Divideandconquer algorithms 49 Fast Fourier transform To perform a linear transformation, it is necessary to calculate a matrixvector product:Divideandconquer algorithms 50 Fast Fourier transform We can apply a divide and conquer algorithm to this problem – Break the matrixvector product into four matrixvector products, each of half the sizeDivideandconquer algorithms 51 Fast Fourier transform The recurrence relation is: Θ(1) n1   T(n) n   4T Θ(nn ) 1   2   Using Maple: rsolve( T(n) = 4T(n/2) + n, T(1) = 1, T(n) ); n (2 n – 1)Divideandconquer algorithms 52 Discrete Fourier transform To introduce the Fourier transform, we need a little information about complex numbers: 2 – There are two complex numbers z such that z = 1Divideandconquer algorithms 53 Discrete Fourier transform To introduce the Fourier transform, we need a little information about complex numbers: 3 – There are three complex numbers z such that z = 1Divideandconquer algorithms 54 Discrete Fourier transform To introduce the Fourier transform, we need a little information about complex numbers: 4 – There are four complex numbers z such that z = 1Divideandconquer algorithms 55 Discrete Fourier transform To introduce the Fourier transform, we need a little information about complex numbers: 5 – There are five complex numbers z such that z = 1Divideandconquer algorithms 56 Discrete Fourier transform To introduce the Fourier transform, we need a little information about complex numbers: 8 – There are eight complex numbers z such that z = 1 – These are also known as the eighth roots of unity – That root with the smallest nonzero angle is said to be the eighth principle root of unityDivideandconquer algorithms 57 Discrete Fourier transform 1 1 1 1 1   2 3 n1 1wwww  In n dimensions, the 2 4 6 2(n1)  1wwww  Fourier transform matrix is F n 3 6 9 3(n1) 1wwww     n1 2(n1) 3(n1) (n1)(n1)  1wwww  –2pj/n th where w = e is the conjugate n principal root of unityDivideandconquer algorithms 58 Discrete Fourier transform For example, the matrix for the Fourier transform for 4dimensions is 1 1 1 1   11 jj  F 4  1 1 1 1  11jj   th Here, w = –j is the conjugate 4 principal root of unity Note that: – The matrix is symmetric – All the column/row vectors are orthogonal 4 – These create a orthogonal basis for CDivideandconquer algorithms 59 Discrete Fourier transform 2 Any matrixvector multiplication is usually Q(n ) – The discrete Fourier transform is a useful tool in all fields of engineering – In general, it is not possible to speed up a matrixvector multiplication – In this case, however, the matrix has a peculiar shape • That of a very special Vandermonde matrixDivideandconquer algorithms 60 Fast Fourier transform We will now look at the Cooley–Tukey algorithm for calculating the discrete Fourier transform – This fast transform can only be applied the dimension is a power of two – We will look at the 8dimensional transform matrix 11 – The eighth conjugate root of unity isw j 22 2 4 8 – Note that w = –j, w = –1 and w = 1Divideandconquer algorithms 61 Fast Fourier transform This is the 8 × 8 Fourier transform matrix 0 – We will write w instead of 1 so that we can see the pattern – We will number the columns 0, 1, 2, …, 7 0 0 0 0 0 0 0 0 v  wwwwwwww  0   0 1 2 3 4 5 6 7 v wwwwwwww 1   0 2 4 6 8 10 12 14   v wwwwwwww 2   0 3 6 9 12 15 18 21 v wwwwwwww   3 F v 8 0 4 8 12 16 20 24 28   v wwwwwwww 4   0 5 10 15 20 25 30 35 v wwwwwwww   5  0 6 12 18 24 30 36 42  v wwwwwwww 6   0 7 14 21 28 35 42 49   wwwwwwww v   7Divideandconquer algorithms 62 Fast Fourier transform 8 Now by definition, w = 1, so we can make some simplifications 14 8 + 6 8 6 6 – For example, w = w = ww = w n n mod 8 – We may use, w = w 49 49 mod 8 1 – For example, w = w = w 0 0 0 0 0 0 0 0 v  wwwwwwww  0   0 1 2 3 4 5 6 7 v wwwwwwww 1   0 2 4 6 8 10 12 14   v wwwwwwww 2   0 3 6 9 12 15 18 21 v wwwwwwww   3 F v 8 0 4 8 12 16 20 24 28   v wwwwwwww 4   0 5 10 15 20 25 30 35 v wwwwwwww   5  0 6 12 18 24 30 36 42  v wwwwwwww 6   0 7 14 21 28 35 42 49   wwwwwwww v   7Divideandconquer algorithms 63 Fast Fourier transform Now we’ve simplified the matrix with powers on the range 0 to 7 0 0 0 0 0 0 0 0 v  wwwwwwww  0   0 1 2 3 4 5 6 7 v wwwwwwww 1   0 2 4 6 0 2 4 6   v wwwwwwww 2   0 3 6 1 4 7 2 5 v wwwwwwww   3 F v 8 0 4 0 4 0 4 0 4   v wwwwwwww 4   0 5 2 7 4 1 6 3 v wwwwwwww   5  0 6 4 2 0 6 4 2  v wwwwwwww 6   0 7 6 5 4 3 2 1   wwwwwwww v   7Divideandconquer algorithms 64 Fast Fourier transform 4 As 8 is even, w = –1 40 – Thus, we replacew = –w 51 w = –w 62 w = –w 73 w = –w 0 0 0 0 0 0 0 0 v  wwwwwwww  0   0 1 2 3 4 5 6 7 v wwwwwwww 1   0 2 4 6 0 2 4 6   v wwwwwwww 2   0 3 6 1 4 7 2 5 v wwwwwwww   3 F v 8 0 4 0 4 0 4 0 4   v wwwwwwww 4   0 5 2 7 4 1 6 3 v wwwwwwww   5  0 6 4 2 0 6 4 2  v wwwwwwww 6   0 7 6 5 4 3 2 1   wwwwwwww v   7Divideandconquer algorithms 65 Fast Fourier transform Now we may observe some patterns 0 0 0 0 0 0 0 0 v  wwwwwwww  0   0 1 2 3 0 1 2 3 v wwwwwwww 1   0 2 0 2 0 2 0 2   v wwwwwwww 2   0 3 2 1 0 3 2 1 v wwwwwwww   3 F v 8 0 0 0 0 0 0 0 0   v wwwwwwww 4   0 1 2 3 0 1 2 3 v wwwwwwww   5  0 2 0 2 0 2 0 2  v wwwwwwww 6   0 3 2 1 0 3 2 1   wwwwwwww v   7Divideandconquer algorithms 66 Fast Fourier transform 2 Note that the even columns (0, 2, 4, 6) are powers of w 0 0 0 0 0 0 0 0 wwwwwwww  0 2 4 6 0 2 0 2 wwwwww ww  – Note also that F 4 0 4 8 12 0 0 0 0  wwwwwwww  0 6 12 18 0 2 0 2  wwwww www  0 0 0 0 0 0 0 0 v  wwwwwwww  0   0 1 2 3 0 1 2 3 v wwwwwwww 1   0 2 0 2 0 2 0 2   v wwwwwwww 2   0 3 2 1 0 3 2 1 v wwwwwwww   3 F v 8 0 0 0 0 0 0 0 0   v wwwwwwww 4   0 1 2 3 0 1 2 3 v wwwwwwww   5  0 2 0 2 0 2 0 2  v wwwwwwww 6   0 3 2 1 0 3 2 1   wwwwwwww v   7Divideandconquer algorithms 67 Fast Fourier transform The shape of the odd columns (1, 3, 5, 7) is less obvious 0 0 0 0 0 0 0 0 v  wwwwwwww  0   0 1 2 3 0 1 2 3 v wwwwwwww 1   0 2 0 2 0 2 0 2   v wwwwwwww 2   0 3 2 1 0 3 2 1 v wwwwwwww   3 F v 8 0 0 0 0 0 0 0 0   v wwwwwwww 4   0 1 2 3 0 1 2 3 v wwwwwwww   5  0 2 0 2 0 2 0 2  v wwwwwwww 6   0 3 2 1 0 3 2 1   wwwwwwww v   7Divideandconquer algorithms 68 Fast Fourier transform 0 0 0 0 0 0 0 0  wwwwwwww  0 1 2 3 0 1 2 3 wwwwwwww  0 2 0 2 0 2 0 2  wwwwwwww  0 3 2 1 0 3 2 1 wwwwwwww Let’s rearrange the  F 8 0 0 0 0 0 0 0 0  wwwwwwww  columns of the matrix and 0 1 2 3 0 1 2 3 wwwwwwww   0 2 0 2 0 2 0 2 wwwwwwww the entries of the vector  0 3 2 1 0 3 2 1  wwwwwwww  1 3 5 7 0 2 4 6 0 0 0 0 0 0 0 0 v  wwwwwwww  0   0 2 0 2 1 3 1 3 v wwwwwwww 2   0 0 0 0 2 2 2 2   v wwwwwwww 4   0 2 0 2 3 1 3 1 v wwwwwwww   6   F v 8 0 0 0 0 0 0 0 0   v wwww wwww 1   0 2 0 2 1 3 1 3 v wwwwwwww   3  0 0 0 0 2 2 2 2  v wwwwwwww 5   0 2 0 2 3 1 3 1   wwwwwwww v   7Divideandconquer algorithms 69 Fast Fourier transform th Recall that w is the 8 conjugate root of unity 2 th – Therefore, w is the 4 conjugate root of unity – Both these matrices are the Fourier transform for a 4dimensional vector 0 0 0 0 0 0 0 0 v  wwwwwwww  0   0 2 0 2 1 3 1 3 v wwwwwwww 2   0 0 0 0 2 2 2 2   v wwwwwwww 4   0 2 0 2 3 1 3 1 v wwwwwwww   6   F v 8 0 0 0 0 0 0 0 0   v wwww wwww 1   0 2 0 2 1 3 1 3 v wwwwwwww   3  0 0 0 0 2 2 2 2  v wwwwwwww 5   0 2 0 2 3 1 3 1   wwwwwwww v   7Divideandconquer algorithms 70 Fast Fourier transform We will label these two blocks as F 4 0 0 0 0 0 0 0 0 v  wwwwwwww  0   0 2 0 2 1 3 1 3 v wwwwwwww 2   F 0 0 4 0 0 2 2 2 2   v wwwwwwww 4   0 2 0 2 3 1 3 1 v wwwwwwww   6   F v 8 0 0 0 0 0 0 0 0   v wwww wwww 1   0 3 0 2 1 3 1 3 v wwwwwwww   3 F  0 0 4 0 0 2 2 2 2  v wwwwwwww 5   0 2 0 2 3 1 3 1   wwwwwwww v   7Divideandconquer algorithms 71 Fast Fourier transform There is one obvious pattern in the second pair of matrices – The bottom matrix is the negative of the top – The other pattern is more subtle 0 0 0 0 0 0 0 0 v  wwwwwwww  0   0 2 0 2 1 3 1 3 v wwwwwwww 2   F 0 0 4 0 0 2 2 2 2   v wwwwwwww 4   0 2 0 2 3 1 3 1 v wwwwwwww   6   F v 8 0 0 0 0 0 0 0 0   v wwww wwww 1   0 3 0 2 1 3 1 3 v wwwwwwww   3 F  0 0 4 0 0 2 2 2 2  v wwwwwwww 5   0 2 0 2 3 1 3 1   wwwwwwww v   7Divideandconquer algorithms 72 Fast Fourier transform 0 0 0 0 0 0 0 0 0 The top matrix w 0 0 0wwwwwwww  1 0 2 0 2 1 3 1 3 is a diagonal 0w 0 0wwwwwwww   2 0 0 0 0 2 2 2 2  multiplied by F 0 0w 0wwwwwwww 4  3 0 2 0 2 3 1 3 1  0 0 0wwwwwwwww  0 0 0 0 0 0 0 0 v  wwwwwwww  0   0 2 0 2 1 3 1 3 v wwwwwwww 2   F 0 0 4 0 0 2 2 2 2   v wwwwwwww 4   0 2 0 2 3 1 3 1 v wwwwwwww   6   F v 8 0 0 0 0 0 0 0 0   v wwww wwww 1   0 3 0 2 1 3 1 3 v wwwwwwww   3 F  0 0 4 0 0 2 2 2 2  v wwwwwwww 5   0 2 0 2 3 1 3 1   wwwwwwww v   7Divideandconquer algorithms 73 Fast Fourier transform 0  w 0 0 0  1 0w 0 0  Represent that diagonal matrix by D 4 2  0 0w 0 – Recall that multiplying a vector  3  by a diagonal matrix is Q(n) 0 0 0w  0 0 0 0 0 0 0 0 v  wwwwwwww  0   0 2 0 2 1 3 1 3 v wwwwwwww 2   F D F 0 0 4 0 0 2 2 4 4 2 2   v wwwwwwww 4   0 2 0 2 3 1 3 1 v wwwwwwww   6   F v 8 0 0 0 0 0 0 0 0   v wwww wwww 1   0 3 0 2 1 3 1 3 v wwwwwwww   3 F  0 0 4 0 0 2 2 2 2  v wwwwwwww 5   0 2 0 2 3 1 3 1   wwwwwwww v   7Divideandconquer algorithms 74 Fast Fourier transform From our previous observation, the bottom matrix is –D F 4 4 0 0 0 0 0 0 0 0 v  wwwwwwww  0   0 2 0 2 1 3 1 3 v wwwwwwww 2   F D F 0 0 4 0 0 2 2 4 4 2 2   v wwwwwwww 4   0 2 0 2 3 1 3 1 v wwwwwwww   6   F v 8 0 0 0 0 0 0 0 0   v wwww wwww 1   0 3 0 2 1 3 1 3 v wwwwwwww   3 F –D F  0 0 4 0 0 2 2 4 4 2 2  v wwwwwwww 5   0 2 0 2 3 1 3 1   wwwwwwww v   7Divideandconquer algorithms 75 Fast Fourier transform Thus, our adjusted Fourier transform matrix is a block matrix consisting of four 4 × 4 matrices 0 0 0 0 0 0 0 0 v  wwwwwwww  0   0 2 0 2 1 3 1 3 v wwwwwwww 2   F D F 0 0 4 0 0 2 2 4 4 2 2   v wwwwwwww 4   0 2 0 2 3 1 3 1 v wwwwwwww   6   F v 8 0 0 0 0 0 0 0 0   v wwww wwww 1   0 3 0 2 1 3 1 3 v wwwwwwww   3 F –D F  0 0 4 0 0 2 2 4 4 2 2  v wwwwwwww 5   0 2 0 2 3 1 3 1   wwwwwwww v   7Divideandconquer algorithms 76 Fast Fourier transform Let’s split up the vector into two vectors 0 0 0 0 0 0 0 0 v  0  wwwwwwww   0 2 0 2 1 3 1 3 v 2 wwwwwwww    v 0 F D F  0 0 4 0 0 2 2 4 4 2 2 v  4 wwwwwwww   0 2 0 2 3 1 3 1 v 6  wwwwwwww   F 8 0 0 0 0 0 0 0 0  wwww wwww v  1  0 3 0 2 1 3 1 3  wwwwwwww  v 3  F–D F  v  0 0 4 0 0 2 2 4 4 2 2 1 wwwwwwww  v  5 0 2 0 2 3 1 3 1   wwwwwwww  v  7Divideandconquer algorithms 77 Fast Fourier transform 4 × 4 matrices Thus, we have the relation: 4dimensional vectors  F DF v   4 4 4 0   v F   8  FDF v 4 4 4  1  F DF   v FvvDF  4 44 0 401 44   Fv Thus,   8  FDF   v FvvDF 4 4 4  1 4 0 44 1   D Fv DF v Note that we want to calculate   and not  nn 1 nn 1 2 – The first is Q(n + T (n)), the second Q(n + T (n)) F F – That is, calculate the FFT of  (a vector) and then multiply the entries v 1 of that vector by the diagonal entriesDivideandconquer algorithms 78 Fast Fourier transform  Fv Fv Now we must calculate and recursively 41 40  – Calculating D F v and  D F v are both Q(n) operations  4 4 1 4 4 1  FvD Fv  – Adding and F v  D F v are also both Q(n)   4 0 4 4 1 4 0 4 4 1 rr  00 – Rearranging the results is also Q(n)  rr 14  F D F   vFvD Fv  rr  4 4 4 0 4 0 4 4 1 21   Fv    8   FD F rr   v FvD Fv  35 4 4 4  1 4 0 4 4 1  Fv 8  rr 42  rr  56  rr 63   rr 77 Divideandconquer algorithms 79 Fast Fourier transform Thus, we have that the time T(n) requires that we – Divide the vector v into the vectors  and vQ(n) v 1 0  – Calculate Fv and Fv recursively 2 T(n/2) 40 41  – Calculate D F v and  D F v Q(n) 4 4 1 4 4 1  – Add F v  D F v and  FvDFv Q(n) 4 0 4 4 1 4 0 4 4 1 Q(n) – Reorder the results to get the result F v 8 The recurrence relation now Q (1) n 1   T(n) n   2TQ(nn )1   2   – This is the runtime of merge sort: Q(n ln(n))Divideandconquer algorithms 80 Fast Fourier transform An argument that this generalizes for other powers of two: 2 F – The even columns of are powers of w n 2 0 2 4 6 8 wwwww ··· 0 4 8 12 16 wwwww ··· – The normalized bottom halves equal the top halves – The odd columns are of the form 0 3 6 9 12 wwwww ··· 0 5 10 15 20 wwwww ··· – These can be written as 0 0 1 2 2 4 3 6 4 8 w ·ww ·ww ·ww · ww · w ··· 0 0 1 4 2 8 3 12 4 16 w ·ww ·ww ·ww ·ww ·w ··· n 1 2 – The normalized bottom halves are the top halves multiplied by w 1Divideandconquer algorithms 81 Fast Fourier transform void FFT( std::complexdouble array, int n ) if ( n == 1 ) return; Q(1)   std::complexdouble evenn/2; Q(1)  std::complexdouble oddn/2;   for ( int k = 0; k n/2; ++k )  evenk = array2k; Q() n  oddk = array2k + 1;    FFT( even, n/2 ); n  2T  FFT( odd, n/2 ); 2  double const PI = 4.0std::atan( 1.0 );  std::complexdouble w = 1.0; Q(1)  std::complexdouble wn = std::exp( std::complexdouble( 0.0, 2.0PI/n ) );  for ( int k = 0; k n/2; ++k )  arrayk = evenk + woddk;  Q() n arrayn/2 + k = evenk woddk;  w = w wn;   Divideandconquer algorithms 82 Divide and Conquer We have now looked at a number of divideandconquer algorithms, and come up with a number of different run times: Binary search T(n) = T(n/2) + Q(1) O(ln(n)) Tree traversals T(n) = 2T(n/2) + Q(1)Q(n) Merge sort T(n) = 2T(n/2) + Q(n)Q(n ln(n)) lg(3) Orderedmatrix search T(n) = 3T(n/2) + Q(1) O(n ) lg(3) Integer multiplication T(n) = 3T(n/2) + Q(n) Q(n ) log (5) 3 Toom3 integer multiplication T(n) = 5T(n/3) + Q(n) Q(n ) 2 lg(7) Matrix multiplication T(n) = 7T(n/2) + Q(n ) Q(n ) Fast Fourier transform T(n) = 2T(n/2) + Q(n) Q(n ln(n))Divideandconquer algorithms 83 The master theorem We used Maple to solve the recurrence relationships We will now solve the general problem 1 n 1   n  T(n) k  a TO(n ) n 1   b  Divideandconquer algorithms 84 The master theorem m In all cases when b = 2, we assumed n = 2 That is, n = 1, 2, 4, 8, 16, 32, 64, .... and interpolated the intermediate resultsDivideandconquer algorithms 85 The master theorem m In this case, we will assume n = b , as we are dividing each interval into b equal parts 2 3 n = 1, b, b , b , ... As before, we will interpolate intermediate behaviour m – Thus, we will solve T(b ) and use this to approximate T(n)Divideandconquer algorithms 86 The master theorem Thus, given the recurrence relation 1 n 1   n  T(n) k  a TO(n ) n 1   b   we have that m  k b m m   T(n) Tb a TOb    b k  b is a constant We can rewrite this as: m m m1 k  Tb aTbOb  Divideandconquer algorithms 87 The master theorem Therefore, we may iterate: m m m1 k  T b a T b b m1 m m2 k k   a a Tbbb   m1 m 2 m2 k k  a Tb abb m2 m1 m 3 m3 2 k k k  a Tb ab abb m3 m2 m1 m 4 m4 3 k 2 k k k  a Tb ab ab abb Divideandconquer algorithms 88 The master theorem Determining a pattern is possible, however, we can determine the m pattern more easily if we divide both sides by a : m m m1 k Tb a Tbb  m m m a a a We can simplify this to: m m m1 k  Tb Tb b   m m1  a a a Divideandconquer algorithms 89 The master theorem We can repeatedly calculate this formula for smaller and smaller values of m: m m m1 k  Tb Tb b   m m1  a a a  m1 m1 m2 k  Tb Tb b   m1 m2  a a a  m2 m2 m3 k  Tb Tb b   m2 m3  a a a  m3 m3 m4 k  Tb Tb b   m3 m4  a a a Divideandconquer algorithms 90 The master theorem Thus, we may carry on m m m1 k  Tb Tb b   m m1 a a a  m1 m1 m2 k  Tb Tb b   m1 m2  a a a  m2 m2 m3 k  Tb Tb b   m2 m3 a a a   2 2 1 k  Tb Tb b   2 1 a a a  1 1 0 k  Tb Tb b   1 0  a a a Divideandconquer algorithms 91 The master theorem A telescoping series is any series of the form n a a a a   k k10 n k1 nn1 Alternatively, if aa  , it follows that aa  kk n 0 kk  10 More generally, we have: nn a a b a a b   k k10 k n k kk  11Divideandconquer algorithms 92 The master theorem m m m1 k  Tb Tb b   m m1  a a a Thus, we find:  m1 m1 m2 k  Tb Tb b   m1 m2 a a a  m2 m2 m3 k  Tb Tb b   m2 m3  a a a   2 2 1 k  Tb Tb b   2 1  a a a  1 1 0 k  Tb Tb b   + 1 0  a a a   m 0 k m TTbb   b   m 0 a a a 1 Divideandconquer algorithms 93 The master theorem We can sum these:  m m 0 k  Tb Tb b    m 0  a a a  1 and simplify:  m m k  Tb b   T1  m  a a  1  m m k k  b b   1   a a  10Divideandconquer algorithms 94 The master theorem m We multiply by a to get  k m  b mm Tba   a 0 Divideandconquer algorithms 95 The master theorem The sum is a geometric series, and the actual value will depend on the ratio Recall that for a geometric series, if r 1 then the series converges:  1  r  1 r 1Divideandconquer algorithms 96 The master theorem Also, if r = 1, we have: m m  1 1 m1  00 If r 1, we can only determine a finite sum: m m1 m1 1 r r1  r  1 r r1 0Divideandconquer algorithms 97 The master theorem Thus, we consider three possible cases k b k  1 b a a k b k b a  1 a k k b b a  1 aDivideandconquer algorithms 98 The master theorem These may be roughly translated into: – The number of recursions at each step is more significant than the k amount of work at each step (b a) k – The contributions are equal (b = a) – The amount of work at each step is more significant than the additional k work contributed by the recursion (b a)Divideandconquer algorithms 99 k b a Which examples fall in this case k a b k b Traversal 2 2 0 1 Quaternary search of an ordered matrix 3 2 0 1 Karatsuba’s integermultiplication algorithm 3 2 1 2 Toom3 integermultiplication algorithm 5 3 1 3 7 2 2 4 Strassen’s matrixmultiplication algorithmDivideandconquer algorithms 100 k b a In this case,  m k k  b b m m m  Tn a a ca   a a  00   k  b 1  c where is a constant  k  a b  0 1 a which we may asymptotically ignoreDivideandconquer algorithms 101 k b a m Therefore, T(n) = O(a ) m By assumption, n = b , hence m =log n and therefore b log n log a b b T(n) = O(a ) = O(n ) Divideandconquer algorithms 102 k b a Going back to our examples: k Run time a b k b log (a) b Traversal 2 2 0 1 1.000 O(n) 1.585 Quaternary search of an ordered matrix 3 2 0 1 1.585 O(n ) 1.585 3 2 1 2 1.465 O(n ) Karatsuba’s integermultiplication algorithm 1.465 Toom3 integermultiplication algorithm 5 3 1 3 1.465 O(n ) 2.807 Strassen’s matrixmultiplication algorithm 7 2 2 4 2.807 O(n )Divideandconquer algorithms 103 k b = a Which examples fall in this case k a b k b Binary search 1 2 0 1 Merge sort 2 2 1 2 Fast Fourier transform 2 2 1 2Divideandconquer algorithms 104 k b = a  m m k  b m m m  Tn a a 1 (m1)a In this case,   a  00 m Therefore, T(n) = O(ma ) m k By assumption, n = b and a = b ∴ m = log n and k = log a b b m HenceTO n ma   m k  O log nb    b k m  O log nb   b  k  O log nn   b log a  b  O log nn   bDivideandconquer algorithms 105 k b = a Going back to our examples: k Run time a b k b Binary search 1 2 0 1 O(1·ln(n)) Merge sort 2 2 1 1 O(n ln(n)) 2 2 1 2 O(n ln(n)) Fast Fourier transformDivideandconquer algorithms 106 k b a We haven’t seen any examples that fall into this case – Suppose we divide the problem into two, but we must perform a linear operation to determine which half to recursively call k a b k b Sample 1 2 1 2Divideandconquer algorithms 107 k b a m1 k  In this case, b  1  m  k  a b m m  Tn a a  k  a b  0 1 a Factor out the constant term and simplify to get: m1  k  1 b 1 1  m m km m  Tn a a b a k k   a a b b  1  11 k b a a Both positive constants (see assumption)Divideandconquer algorithms 108 k b a m m Recall that if p q then p = o(q ), hence m k m a = o((b ) ) Thus, we can ignore the second term: km m km T(n) = O(b – a ) = O(b ) m Again, by assumption, n = b , hence m k k T(n) =O((b ) ) = O(n )Divideandconquer algorithms 109 k b a Going back to our example: k Run time a b k b 1 Sample 1 2 1 2 O(n ) The linear operation contributes more than the divideandconquer componentDivideandconquer algorithms 110 Summary of cases To summarize these run times: k b log a b  1 O(n ) a k b log a k b O(log (n) n )O(log (n) n )  1 b b a i.e., k log (a) b k k b O(n )  1 aDivideandconquer algorithms 111 Summary Therefore: – If the amount of work being done at each step to either subdivide the problem or to recombine the solutions dominates, then this is the run k time of the algorithm: O(n ) k – If the problem is being divided into many small subproblems (a b ) log (a) b then the number of subproblems dominates: O(n ) – In between, a little more (logarithmically more) work must be doneDivideandconquer algorithms 112 References Wikipedia, http://en.wikipedia.org/wiki/Divideandconquer These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W. Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.
Website URL
Comment