Report

A simple example • finding the maximum of a set S of n numbers Time complexity • Time complexity: 2T (n/2)+1 , n>2 T (n)= 1 , n2 • Calculation of T(n): Assume n = 2k, T(n) = 2T(n/2)+1 = 2(2T(n/4)+1)+1 = 4T(n/4)+2+1 : k-1 =2 T(2)+2k-2+…+4+2+1 =2k-1+2k-2+…+4+2+1 =2k-1 = n-1 A general divide-and-conquer algorithm Step 1: If the problem size is small, solve this problem directly; otherwise, split the original problem into 2 sub-problems with equal sizes. Step 2: Recursively solve these 2 sub-problems by applying this algorithm. Step 3: Merge the solutions of the 2 subproblems into a solution of the original problem. Time complexity of the general algorithm • Time complexity: T (n)= 2T (n/2)+ S (n)+ M (n) b where S(n) : time for splitting M(n) : time for merging b : a constant c : a constant • e.g. Binary search • e.g. quick sort • e.g. merge sort ,nc ,n<c Divide and Conquer • Divide-and-conquer method for algorithm design: – Divide: if the input size is too large to deal with in a straightforward manner, divide the problem into two or more disjoint subproblems – Conquer: use divide and conquer recursively to solve the subproblems – Combine: take the solutions to the subproblems and “merge” these solutions into a solution for the original problem Recurrences • Running times of algorithms with Recursive calls can be described using recurrences • A recurrence is an equation or inequality that describes a function in terms of its value on smaller inputs solving_trivial_problem if n 1 T (n) num _pieces T ( n / subproblem _size_factor ) dividing com bining if n 1 • Example: Merge Sort (1) if n 1 T (n) 2T ( n / 2) ( n ) if n 1 Solving Recurrences • Repeated substitution method – Expanding the recurrence by substitution and noticing patterns • Substitution method – guessing the solutions – verifying the solution by the mathematical induction • Recursion-trees • Master method – templates for different classes of recurrences Repeated Substitution Method • Let’s find the running time of merge sort (let’s assume that n=2b, for some b). 1 if n 1 T (n) 2T ( n / 2) n if n 1 T (n) T (n) 2T n / 2 n 2 2T n / 4 n / 2 n 2 T ( n / 4) 2 n 2 (2 T ( n / 8) n / 4) 2 n 2 T ( n / 8) 3 n 2 T ( n / 2 ) in 2 2 2 3 i lg n substitute expand substitute expand observe the patte rn i T ( n / n ) n lg n n n lg n Repeated Substitution Method • The procedure is straightforward: – – – – – – Substitute Expand Substitute Expand … Observe a pattern and write how your expression looks after the i-th substitution – Find out what the value of i (e.g., lgn) should be to get the base case of the recurrence (say T(1)) – Insert the value of T(1) and the expression of i into your expression Integer Multiplication • Algorithm: Multiply two n-bit integers I and J. – Divide step: Split I and J into high-order and low-order bits I Ih 2 n/2 J Jh2 n/2 Il Jl – We can then define I*J by multiplying the parts and adding: I * J (Ih 2 n/2 Il ) * (J h 2 IhJh 2 IhJl 2 n n/2 n/2 Jl) Il J h 2 n/2 Il J l – So, T(n) = 4T(n/2) + n, which implies T(n) is O(n2). – But that is no better than the algorithm we learned in grade school. An Improved Integer Multiplication Algorithm • Algorithm: Multiply two n-bit integers I and J. – Divide step: Split I and J into high-order and low-order bits I Ih 2 n/2 Il J Jh2 Jl – Observe that there is a different way to multiply parts: n/2 I * J I h J h 2 [( I h I l )( J l J h ) I h J h I l J l ] 2 n n/2 Il Jl I h J h 2 [( I h J l I l J l I h J h I l J h ) I h J h I l J l ] 2 n I h J h 2 ( I h J l I l J h )2 n n/2 n/2 Il J l – So, T(n) = 3T(n/2) + n, which implies T(n) is O(nlog23), by the Master Theorem. – Thus, T(n) is O(n1.585). Il J l Matrix multiplication • Let A, B and C be n n matrices C = AB C(i, j) = A(i, k)B(k, j) 1 k n • The straightforward method to perform a matrix multiplication requires O(n3) time. Divide-and-conquer approach • C = AB C 11 C 12 C 21 C 22 = = A 11 A 12 A 21 A 22 B 11 B 12 B 21 B 22 C11 = A11 B11 + A12 B21 C12 = A11B12 + A12 B22 C21 = A21 B11 + A22 B21 C22 = A21 B12 + A22 B22 • Time complexity: (# of additions : n2) We get T(n) = O(n3) T (n ) = b ,n 2 2 8 T (n /2 )+ cn , n > 2 Strassen’s matrix multiplicaiton • P = (A11 + A22)(B11 + B22) Q = (A21 + A22)B11 R = A11(B12 - B22) S = A22(B21 - B11) T = (A11 + A12)B22 U = (A21 - A11)(B11 + B12) V = (A12 - A22)(B21 + B22). • C11 = P + S - T + V C12 = R + T C21 = Q + S C22 = P + R - Q + U Time complexity • 7 multiplications and 18 additions or subtractions • Time complexity: b ,n 2 T (n) = 2 7T (n/2)+ an , n > 2 T(n) = an2 + 7T(n/2) = an2 + 7(a(n/2)2 + 7T(n/4)) = an2 + (7/4)an2 + 72T(n/4) =… : = an2(1 + 7/4 + (7/4)2+…+(7/4)k-1+7kT(1)) cn2(7/4)log2n+7log2n, c is a constant = cnlog24+log27-log24 +nlog27 = O(nlog27) O(n2.81) Median Finding • Given a set of "n" unordered numbers we want to find the "k th" smallest number. (k is an integer between 1 and n). A Simple Solution • A simple sorting algorithm like heapsort will take Order of O(nlg2n) time. Step Sort n elements using heapsort Return the kth smallest element Total running time Running Time O(nlog2n) O(1) O(nlog2n) Linear Time selection algorithm • Also called Median Finding Algorithm. • Find k th smallest element in O (n) time in worst case. • Uses Divide and Conquer strategy. • Uses elimination in order to cut down the running time substantially. Steps to solve the problem • Step 1: If n is small, for example n<6, just sort and return the kth smallest number in constant time i.e; O(1) time. • Step 2: Group the given number in subsets of 5 in O(n) time. • Step3: Sort each of the group in O (n) time. Find median of each group. • Given a set (……..2,5,9,19,24,54,5,87,9,10,44,32,21,13,24, 18,26,16,19,25,39,47,56,71,91,61,44,28………) having n elements. Arrange the numbers in groups of five ……………….. ……………….. ……………….. ……………….. ……………….. 2 5 54 44 4 25 5 32 18 39 21 26 47 ……………….. ……………….. ……………….. 9 87 19 9 13 16 56 ……………….. 24 10 2 19 71 ……………….. Find median of N/5 groups ……………….. ……………….. ……………….. ……………….. ……………….. 2 5 5 2 4 9 13 16 25 39 ……………….. ……………….. ……………….. 9 10 21 18 47 19 54 32 19 56 ……………….. 24 87 44 26 71 ……………….. Median of each group Find the Median of each group ……………….. 3.n/10 ……………….. ……………….. ……………….. ……………….. 2 5 5 2 4 25 9 13 16 39 ……………….. ……………….. ……………….. 9 10 21 18 47 19 54 32 19 56 ……………….. 24 87 44 26 71 ……………….. Find m ,the median of medians Find the sets L and R • Compare the n-1 elements with the median m and find two sets L and R such that every element in L is smaller than m and every element in R is greater than m. m L 3n/10<L<7n/10 R 3n/10<R<7n/10 Description of the Algorithm step • If n is small, for example n<6, just sort and return the k the smallest number.(time- 7) • If n>5, then partition the numbers into groups of 5.(time n) • Sort the numbers within each group. Select the middle elements (the medians). (time- 7n/5) • Call your "Selection" routine recursively to find the median of n/5 medians and call it m. (time-Tn/5) • Compare all n-1 elements with the median of medians m and determine the sets L and R, where L contains all elements <m, and R contains all elements >m. Clearly, the rank of m is r=|L|+1 (|L| is the size of L) (timen) Contd…. • If k=r, then return m • If k<r, then return k th smallest of the set L .(time T7n/10) • If k>r, then return k-r th smallest of the set R. Recursive formula • T (n)=O(n) + T(n/5) +T(7n/10) We will solve this equation in order to get the complexity. We assume that T (n)< C*n T (n)= a*n + T (n/5) + T (7n/10) <= C*n/5+ C*7*n/10 + a*n <= C*n if 9*C/10 +a <= C Which implies C >= 10*a Hence 10*a*n satisfies the recurrence and so T(n) is O(n) 2-D ranking finding • Def: Let A = (a1,a2), B = (b1,b2). A dominates B iff a1> b1 and a2 > b2 • Def: Given a set S of n points, the rank of a point x is the number of points dominated by x. D B A C E rank(A)= 0 rank(B) = 1 rank(C) = 1 rank(D) = 3 rank(E) = 0 Straightforward algorithm: compare all pairs of points : O(n2) Divide-and-conquer 2-D ranking finding Input: A set S of planar points P1,P2,…,Pn Output: The rank of every point in S Step 1: (Split the points along the median line L into A and B.) a. If S contains only one point, return its rank as 0. b. Else, choose a cut line L perpendicular to the x-axis such that n/2 points of S have x-values L (call this set of points A) and the remainder points have x-values L(call this set B). Note that L is a median x-value of this set. Step 2: Find ranks of points in A and ranks of points in B, recursively. Step 3: Sort points in A and B according to their y-values. Scan these points sequentially and determine, for each point in B, the number of points in A whose y-values are less than its y-value. The rank of this point is equal to the rank of this point among points in B, plus the number of points in A whose y-values are less than its y-value. time complexity : step 1 : O(n) step 3 : O(n log n) (finding median) (sorting) total time complexity : T(n) 2T( n ) + c1 n log n + c2 n 2 n 2T( ) + c n log n 2 n 4T( ) + c n log n + c n log n 4 2 nT(1) + c(n log n + n log n +n log n +…+n log 2) 2 nT(1) + 2 cn log n 4 2-D maxima finding problem • Def : A point (x1, y1) dominates (x2, y2) if x1 > x2 and y1 > y2. A point is called a maxima if no other point dominates it • Straightforward method : Compare every pair of points. Time complexity: O(n2) Divide-and-conquer for maxima finding The maximal points of SL and SR The algorithm: • Input: A set of n planar points. • Output: The maximal points of S. Step 1: If S contains only one point, return it as the maxima. Otherwise, find a line L perpendicular to the X-axis which separates the set of points into two subsets SLand SR , each of which consisting of n/2 points. Step 2: Recursively find the maximal points of SL and SR . Step 3: Find the largest y-value of SR. Project the maximal points of SL onto L. Discard each of the maximal points of SL if its y-value is less than the largest y-value of SR . • Time complexity: T(n) Step 1: O(n) Step 2: 2T(n/2) Step 3: O(n) T(n)= 2T(n/2)+O (n)+O (n ) 1 Assume n = 2k T(n) = O(n log n) ,n>1 ,n=1 The closest pair problem • Given a set S of n points, find a pair of points which are closest together. 2-D version • 1-D version : Solved by sorting Time complexity : O(n log n) • at most 6 points in area A: The algorithm: • Input: A set of n planar points. • Output: The distance between two closest points. Step 1: Sort points in S according to their y-values and x-values. Step 2: If S contains only two points, return infinity as their distance. Step 3: Find a median line L perpendicular to the Xaxis to divide S into two subsets, with equal sizes, SL and SR. Step 4: Recursively apply Step 2 and Step 3 to solve the closest pair problems of SL and SR. Let dL(dR) denote the distance between the closest pair in SL (SR). Let d = min(dL, dR). Step 5: For a point P in the half-slab bounded by L-d and L, let its y-value by denoted as yP . For each such P, find all points in the half-slab bounded by L and L+d whose y-value fall within yP +d and yP d. If the distance d between P and a point in the other half-slab is less than d, let d=d . The final value of d is the answer. • Time complexity: O(n log n) Step 1: O(n log n) Steps 2~5: T(n)= 2T(n/2)+O (n)+O (n) 1 T(n) = O(n log n) ,n>1 ,n=1 The convex hull problem concave polygon: convex polygon: • The convex hull of a set of planar points is the smallest convex polygon containing all of the points. • The divide-and-conquer strategy to solve the problem: • The merging procedure: 1. 2. Select an interior point p. There are 3 sequences of points which have increasing polar angles with respect to p. (1) g, h, i, j, k (2) a, b, c, d (3) f, e Merge these 3 sequences into 1 sequence: g, h, a, b, f, c, e, d, i, j, k. Apply Graham scan to examine the points one by one and eliminate the points which cause reflexive angles. 3. 4. • e.g. points b and f need to be deleted. Final result: Divide-and-conquer for convex hull • Input : A set S of planar points • Output : A convex hull for S Step 1: If S contains no more than five points, use exhaustive searching to find the convex hull and return. Step 2: Find a median line perpendicular to the X-axis which divides S into SL and SR ; SL lies to the left of SR . Step 3: Recursively construct convex hulls for SL and SR. Denote these convex hulls by Hull(SL) and Hull(SR) respectively. • Step 4: Apply the merging procedure to merge Hull(SL) and Hull(SR) together to form a convex hull. • Time complexity: T(n) = 2T(n/2) + O(n) = O(n log n) The Fast Fourier Transform 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Outline • • • • Polynomial Multiplication Problem Primitive Roots of Unity The Discrete Fourier Transform The FFT Algorithm Polynomials • Polynomial: p( x) 5 2 x 8x 3x 4 x 2 3 4 • In general, n 1 p( x) ax i i i0 or p ( x ) a 0 a 1 x a 2 x a n 1 x 2 n 1 Polynomial Evaluation • Horner’s Rule: – Given coefficients (a0,a1,a2,…,an-1), defining polynomial n 1 p( x) ai x i i0 – Given x, we can evaluate p(x) in O(n) time using the equation p ( x ) a 0 x ( a1 x ( a 2 x ( a n 2 xa n 1 ) )) • Eval(A,x): [Where A=(a0,a1,a2,…,an-1)] – If n=1, then return a0 – Else, • Let A’=(a1,a2,…,an-1) [assume this can be done in constant time] • return a0+x*Eval(A’,x) Polynomial Multiplication • Given coefficients (a0,a1,a2,…,an-1) and (b0,b1,b2,…,bn-1) defining two polynomials, p() and q(), and number x, compute p(x)q(x). • Horner’s rule doesn’t help, since n 1 p( x )q( x ) cx i i i0 where i ci a j b i j j0 • A straightforward evaluation would take O(n2) time. The “magical” FFT will do it in O(n log n) time. Polynomial Interpolation & Polynomial Multiplication • Given a set of n points in the plane with distinct x-coordinates, there is exactly one (n-1)-degree polynomial going through all these points. • Alternate approach to computing p(x)q(x): – Calculate p() on 2n x-values, x0,x1,…,x2n-1. – Calculate q() on the same 2n x values. – Find the (2n-1)-degree polynomial that goes through the points {(x0,p(x0)q(x0)), (x1,p(x1)q(x1)), …, (x2n-1,p(x2n-1)q(x2n-1))}. • Unfortunately, a straightforward evaluation would still take O(n2) time, as we would need to apply an O(n)-time Horner’s Rule evaluation to 2n different points. • The “magical” FFT will do it in O(n log n) time, by picking 2n points that are easy to evaluate… Primitive Roots of Unity • A number w is a primitive n-th root of unity, for n>1, if – – • • wn = 1 The numbers 1, w, w2, …, wn-1 are all distinct Example 1: x 1 2 3 4 5 6 7 8 9 10 x^2 1 4 9 5 3 3 5 9 4 1 x^3 1 8 5 9 4 7 2 6 3 10 x^4 1 5 4 3 9 9 3 4 5 1 x^5 1 10 1 1 1 10 10 10 1 10 x^6 1 9 3 4 5 5 4 3 9 1 x^7 1 7 9 5 3 8 6 2 4 10 x^8 1 3 5 9 4 4 9 5 3 1 – Z*11: – – – 2, 6, 7, 8 are 10-th roots of unity in Z*11 22=4, 62=3, 72=5, 82=9 are 5-th roots of unity in Z*11 2-1=6, 3-1=4, 4-1=3, 5-1=9, 6-1=2, 7-1=8, 8-1=7, 9-1=5 x^9 1 6 4 3 9 2 8 7 5 10 x^10 1 1 1 1 1 1 1 1 1 1 Example 2: The complex number e2pi/n is a primitive n-th root of unity, where i 1 Properties of Primitive Roots of Unity • Inverse Property: If w is a primitive root of unity, then w -1=wn-1 Proof: wwn-1=wn=1 – • Cancellation Property: For non-zero -n<k<n, w – w (w ) 1 k kj j0 0 w n 1 k (w ) 1 n w k k 1 (1) 1 11 k w k 1 w k 1 0 Reduction Property: If w is a primitve (2n)-th root of unity, then w2 is a primitive n-th root of unity. – • kj j0 Proof: n 1 • n 1 Proof: If 1,w,w2,…,w2n-1 are all distinct, so are 1,w2,(w2)2,…,(w2)n-1 Reflective Property: If n is even, then wn/2 = -1. – Proof: By the cancellation property, for k=n/2: n 1 0 w (n / 2) j w w 0 j0 – Corollary: wk+n/2= -wk. n/2 w w 0 n/2 w w 0 n/2 ( n / 2 )( 1 w n/2 ) The Discrete Fourier Transform • • Given coefficients (a0,a1,a2,…,an-1) for an (n-1)-degree polynomial p(x) The Discrete Fourier Transform is to evaluate p at the values – – – 1,w,w2,…,wn-1 We produce (y0,y1,y2,…,yn-1), where yj=p(wj) n 1 That is, ij y j a iw i0 – • Matrix form: y=Fa, where F[i,j]=wij. The Inverse Discrete Fourier Transform recovers the coefficients of an (n-1)-degree polynomial given its values at 1,w,w2,…,wn-1 – Matrix form: a=F -1y, where F -1[i,j]=w-ij/n. Correctness of the inverse DFT • • The DFT and inverse DFT really are inverse operations Proof: Let A=F -1F. We want to show that A=I, where A[ i , j ] 1 n • w ki w kj k 0 If i=j, then A[ i , i ] 1 n • n 1 n 1 w ki w ki 1 n k 0 n 1 w 0 k 0 1 n 1 n If i and j are different, then A[ i , j ] 1 n n 1 w k 0 ( ji)k 0 (by Cancellati on Property) Convolution • • The DFT and the inverse DFT can be used to multiply two polynomials So we can get the coefficients of the product polynomial quickly if we can compute the DFT (and its inverse) quickly… [a0,a1,a2,...,an-1] [b0,b1,b2,...,bn-1] Pad with n 0's Pad with n 0's [a0,a1,a2,...,an-1,0,0,...,0] [b0,b1,b2,...,bn-1,0,0,...,0] DFT DFT [y0,y1,y2,...,y2n-1] [z0,z1,z2,...,z2n-1] Component Multiply [y0z0,y1z1,...,y2n-1z2n-1] inverse DFT [c0,c1,c2,...,c2n-1] (Convolution) The Fast Fourier Transform • • The FFT is an efficient algorithm for computing the DFT The FFT is based on the divide-and-conquer paradigm: – If n is even, we can divide a polynomial into two polynomials and we can write The FFT Algorithm The running time is O(n log n). [inverse FFT is similar]