lecture #3 - Divide and Conquer Fall 2009

Divide and Conquer • MergeSort – We are given a list of n elements. – Split list into two lists each of length n/2. • More precisely, one with lenth:the other: n .  2   2 – Sort each list using merge sort (recursive call). – Merge the sorted lists to get the final result. • Merge sort analysis: – Let T(n) = number of comparisons to sort n items in the worst case. Note: T(1) = 0, T(2) = 1  0 if n =1  T(n) =        T    +T    +Θ( n ifn >1      • Now what??? Floors and Ceilings • In practice, floors and ceilings are often neglected. • To be mathematically precise, we should not neglect them. • This can nearly always be done, but details can get quite messy. • In this course, we will almost always gloss over them. This is fine for our purposes, but in other settings it might not be (e.g. when writing a formal proof for publication). 1 Solving Recurrences • Method 1: Recursion Trees • Method 2: Master theorem • Method 3: Guessing and Checking method • We will study these in the next unit. For now, we solve the recurrence in an ad-hoc fashion. Simple Merge Sort Analysis • A simple analysis gives us a good guess: k –Assume n = 2 . Then: T(n) < cn + 2T(n/2) < cn + 2{cn/2 + 2T(n/4)} < 2cn + 4T(n/4) = ... (continuing) i i < icn + 2 T(n/2 ) (in general) < kcn + n T(1) (when i is finally k) ▯ T(n) ∈ O(n log n) (since k = log n). 2 A More Thorough Analysis • Write it as  0 if n =1 T(n) ≤   T (n/2  +T )  n/2  +an if n )1 • Prove T(n) < cn log n by induction on n. • Base case: n = 1. True since T(n) = 0. • Inductive step: assume T(k) < ck log k for k < n, and prove true for k = n. Mergesort (cont.)      T n ≤T 2 +T 2+an              ≤ c log  +c  log  +an ≤ c log  +c  logn +n       ≤ c (logn− 1+ c  logn+an     n = cnlogn−c  + an   n 1   c  c ≤ cnlogn−c  − +an = cnlogn+a − n+ 2 2   2  2 ≤ cnlogn for, say, 4a 3 Divide-and-Conquer • A general algorithmic paradigm (strategy) – Divide: • Separate a problem into subproblems. – Conquer: • Solve the subproblems (recursively). – Combine: • Use subproblem results to derive a final result for the original problem • Examples: binary search, quick sort, merge sort When can we use D&C? • Candidates for D&C: – Original problem is easily decomposable into subproblems. • We do not want to see “overlap” in the subproblems. – Combining solutions is not too costly. – Subproblems are about the same size. – We will see some examples of D&C with special emphasis on the analysis of execution time. 4 Multiplication of Large Integers • We illustrate this problem with decimal digits. – An actual implementatio