div_conquer

Algorithm Design Techniques:Divide and Conquer : 

Algorithm Design Techniques:Divide and Conquer

Introduction : 

Introduction Divide and conquer – algorithm makes at least two recursive calls Subproblems should not be overlapping Example: Fibonacci numbers Examples Recursive maximum subsequence sum Linear time tree traversal Mergesort, quicksort

Running Time : 

Running Time Mergesort T(N) = 2T(N/2) + O(N) Theorem: The solution to the equation T(N) = aT(N/b) + ?(Nk) where a>=1 and b>1, is T(N) = O(Nlog ba) a > bk = O(NklogN) a = bk = O(Nk) a < bk

Running Time: Proof : 

Running Time: Proof Let – N=bm N/b=bm-1 Nk=(bm)k=bmk=bkm=(bk)m T(1) = 1 T(bm) = aT(bm-1)+(bk)m - divide by am and use telescoping m T(bm)/am = S(bk/a)i i=0 multiply by am

Running Time: Proof : 

Running Time: Proof m T(bm) = amS(bk/a)i i=0 a > bk – series will converge to a constant T(N) = O(am) = O(alog bN) = O(Nlog ba) a = bk – each term in sum is 1, sum contains 1+logbN terms, logba = k T(N) = O(amlogbN) = O(Nlog balogbN) = O(NklogbN) = O(NklogN) a < bk – each term will be greater than 1 T(N) = am(((bk/a)m+1-1)/((bk/a)-1)) = O(am(bk/a)m) = O((bk)m) = O(Nk)

Running Time : 

Running Time Theorem: If a1+ a2+...+ ak < 1, then the solution to the equation T(N) = T(a1N) + T(a2N) +... + T(akN) +O(N) is T(N) = O(N) Idea: problem is made smaller at every step

Closest-Points Problem : 

Closest-Points Problem p1 = (x1, y1) p2 = (x2, y2) Euclidean distance between p1 and p2 is [(x1-x2)2 + (y1-y2)2]1/2 Goal: Given N points, find closest pair Brute force algorithm?

Closest-Points Example : 

Closest-Points Example

Closest-Points Problem : 

Closest-Points Problem Brute force algorithm? O(N2) Divide and Conquer similar to maximum subsequence sum sort by X coordinate find closest two in left half (dL) find closest two in right half (dR) find closest two where 1 is in left, 1 in right (dC) closest is minimum

Closest-Points Example : 

Closest-Points Example dL dR dC

Closest-Points Problem : 

Closest-Points Problem find closest two where 1 is in left, 1 in right (dC) To ensure O(NlogN) solution, this step must be done in O(N) time d = min(dL, dR) Only need to look at points d from center Still cannot do brute force on these points – what would be running time? Observe: for each point, only need to consider points that are less than d away in y coordinate There are a maximum of 7 points to consider Points must be separated by at least d Don't need to look at points that have already been processed

Example: Worst Case : 

Example: Worst Case

Algorithm: findClosest : 

Algorithm: findClosest T(N) = NlogN + NlogN + 2T(N/2) + 7N (inner loop runs max 7 times) preprocessing step 1: sort by x coordinate preprocessing step 1: sort by y coordinate findClosest(left) findClosest(right) for(i=0; i<numPointsInStrip; i++) for(j=i+1; j<numPointsInStrip;j++) if(y coordinates of pi and pj differ by more than d) break; else if(dist(pi, pj) < d) d = dist(pi, pj)

Selection Problem : 

Selection Problem Find kth smallest element in a collection of N elements Obvious algorithm? Sort, find kth – running time? Can be solved in O(N)

Selection Problem : 

Selection Problem Quickselect partition (as in quicksort) into S1 and S2 if k < size of S1 – quickselect on S1 else if k == size of S1 + 1 – found else quickselect on S2 Running time could still be N2 unless pivot is guaranteed to be chosen wisely

Selection Problem : 

Selection Problem Choosing the pivot Arrange N elements into floor(N/5) groups of 5 elements Find median of each group. This gives a list M of floor(N/5) medians. Sort each set (8 operations) Find median of M. Choose as pivot Call quickselect(M/2) on M elements

Example : 

Example L H H L T T v T T S L T T S L T T S T T S Medians S – small L – large H – huge T – tiny H H H H H H H H

Pivot Selection : 

Pivot Selection 10k+5 = N 2k+1 medians 1 pivot, k L's, and K S's 2k+2 H's, and 2k+2 T's 3k+2 larger than pivot 3k+2 smaller than pivot (10k+5)-(3k+2)-1(pivot) = max 7k+2 in partition < .7N

Running Time: Quickselect : 

Running Time: Quickselect partition into N/5 arrays of size 5 and sort find median of medians (quickselect) – use as pivot partition if pivot is kth element – return else quickselect on appropriate partition T(N) = 8(N/5) + T(.2N) + N + T(.7N) = O(N)

Multiplying Integers : 

Multiplying Integers x = 61,438,521 y = 94,736,407 Typical algorithm is N2 Use divide and conquer! XL=6,143 XR=8,521 YL=9,473 YR=6,407 X = XL104+XR Y = YL104+YR XY = XLYL108 + (XLYR + XRYL)104 + XRYR T(N) = 4T(N/2) + O(N) = O(N2)

Multiplying Integers : 

Multiplying Integers XY = XLYL108 + (XLYR + XRYL)104 + XRYR XLYR + XRYL = (XL – XR)(YR-YL)+XLYL+XRYR Use 1 multiplication plus 2 results already computed T(N) = 3T(N/2) + O(N) T(N) = O(Nlog23) = O(N1.59)

Matrix Multiplication : 

Matrix Multiplication A = 3 4 1 6 B = 5 6 9 3 1 2 5 7 4 5 3 1 5 1 2 9 1 1 8 4 4 3 5 6 3 1 4 1 Ci, j = dot product of ith row of A and jth col of B C0, 0 = (3*5)+(4*4)+(1*1)+(6*3) Brute force algorithm = O(N3)

Matrix Multiplication : 

Matrix Multiplication A1, 1 A1, 2 B1, 1 B1, 2 = C1, 1 C1, 2 A2, 1 A2, 2 B2, 1 B2, 2 C2, 1 C2, 2 C1, 1 = A1, 1 B1, 1 + A1, 2 B2, 1 C1, 2 = A1, 1 B1, 2 + A1, 2 B2, 2 C2, 1 = A2, 1 B1, 1 + A2, 2 B2, 1 C2, 2 = A2, 1 B1, 2 + A2, 2 B2, 2

Matrix Multiplication : 

Matrix Multiplication T(N) = 8T(N/2) + O(N2) additions take N2 Still O(N3) M1 = (A1, 2- A2, 2) (B2, 1+ B2, 2) M2 = (A1, 1+A2, 2) (B1, 1+ B2, 2) M3 = (A1, 1- A2, 1) (B1, 1+ B1, 2) M4 = (A1, 1+ A1, 2) (B2,2) M5 = (A1, 1) (B1,2 -B2,2) M6 = (A2, 2) (B2,1-B1,1) M7 = (A2, 1+ A2, 2) (B1,1)

Matrix Multiplication : 

Matrix Multiplication C1, 1 = M1 + M2 – M4 + M6 C1, 2 = M4 + M5 C2, 1 = M6 + M7 C2, 2 = M2 - M3 + M5 - M7 T(N) = 7T(N/2) + O(N2) = O(Nlog27) = O(N2.81)