Class Notes (837,538)
Canada (510,303)
CS 341 (26)
Lecture

# lecture #3 - Divide and Conquer Fall 2009

8 Pages
72 Views

School
Department
Computer Science
Course
CS 341
Professor
Forbes Burkowski
Semester
Fall

Description
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
More Less

Related notes for CS 341
Me

Log In

OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.

Request Course
Submit