Announcements
Announcements
• Homework 2 due today
• Homework 3 online soon
Last Time
• Divide and Conquer (Ch 2)
1. Break problem into pieces
2. Solve pieces recursively
3. Recombine pieces to get answer
• Karatsuba Multiplication
– Naïve algorithm for multiplying n-bit numbers is
O(n2) time. Can we do better?
Karatsuba
(AX+B)(CX+D) = ACX2+[AD+BC]X+BD
= ACX2+[(A+B)(C+D)-AC-BD]X+BD
Can multiply two n-bit numbers by multiplying 3
pairs of n/2-bit numbers and doing some
arithmetic.
Karatsuba Multiplication
KaratsubaMult(N,M)
If N+M<99, Return Product(N,M) Let X be a power of 2⌊log(N+M)/2⌋ Write N = AX + B, M = CX + D P 1 ← Product(A,C) P 2 ← Product(B,D) P 3 ← Product(A+B,C+D) Return P 1 X2 + [P 3 -P 1 -P 2 ]X + P 3 P 1 ← KaratsubaMult(A,C) P 2 ← KaratsubaMult(B,D) P 3 ← KaratsubaMult(A+B,C+D) O(n) O(n) ??? Today • Karatsuba Multiplication • Master Theorem • Strassen’s Algorithm Runtime Recurrence Karatsuba multiplication on inputs of size n spends O(n) time, and then makes three recursive calls to problems of (approximately) half the size. If T(n) is the runtime for n-bit inputs, we have the recursion: How do we solve this recursion? Recursive Calls n n/2 n/2 n/2 n/4 n/4 n/4 1 1 1 1 n/4 n/4 n/4 n/4 n/4 n/4 1(n) 3(n/2) 9(n/4) 3k(n/2k) 3log(n)(1) log2(n) levels Total Runtime Divide and Conquer This is our first example of this general technique: 1. Break problem into pieces. – Compute AC, BD, (A+B)(C+D) 2. Recursively solve pieces. 3. Recombine to get answer. – NM=ACX2+[(A+B)(C+D)-AC-BD]X+BD Generalization We will often get runtime recurrences with D&C looking something like this: T(n) = O(1) for n = O(1) T(n) = a T(n/b +O(1)) + O(nd) otherwise. We will need to know how to solve these. Tracking Recursive Calls We have: • 1 recursive call of size n • a recursive calls of size n/b+O(1) • a2 recursive calls of size n/b2+O(1) • … • ak recursive calls of size n/bk+O(1) Bottoms out when k = logb(n). Runtime Combining the runtimes from each level of the recursion we get: The asymptotics will depend on whether a/bd is bigger than 1. Case 1: a > bd
Increasing geometric series dominated by last
term. Runtime is dominated by recursive calls
at the bottom level.
Case 2: a < bd Decreasing geometric series is dominated by the first term. Runtime is mostly based on the cleanup steps at the top level. Runtime = O(nd) Case 3: a = bd Every level of the recursion does the same amount of work. Master Theorem Theorem: Let T(n) be given by the recurrence: Then we have that Question: Runtimes Suppose that a divide and conquer algorithm needs to solve 4 recursive subproblems of half the size and do O(n2) additional work. What is the runtime? A) O(n) B) O(n log(n) C) O(n2) D) O(n2 log(n)) E) O(n3) a = 4, b = 2, d = 2. a = bd. So runtime is O(nd log(n)) Note In divide and conquer, it is important that the recursive subcalls are a constant fraction of the size of the original. For example, if we have T(n) = 2T(n-1) then T(n) = O(2n). Matrix Multiplication Problem: Multiply two nxn matrices. Recall: If AB=C then Cij = Σk AikBkj Naïve algorithm computes this sum of n terms, for each of n2 entries. Runtime = O(n3). Can we do better? Block Matrix Multiplication If you divide the matrix into blocks, you can get the product of the full matrix in terms of products of the blocks. Here, A,B,C,… are (n/2)x(n/2) matrices. Easy D&C Compute 8 products of (n/2)x(n/2) matrices, and do some addition to get answer. T(n) = 8T(n/2)+O(n2). Master Theorem: a = 8, b = 2, d = 2. a > bd so O(nC) with C = log28 = 3. O(n
3).
Strassen’s Algorithm
Instead compute:
• M1=(A+D)(E+H)
• M2=(C+D)E
• M3=A(F-H)
• M4=D(G-E)
• M5=(A+B)H
• M6=(C-A)(E+F)
• M7=(B-D)(G+H)
Entries of product matrix
are:
• M1+M4-M5+M7
• M3+M5
• M2+M4
• M1-M2+M3+M6
How do you figure this out?
Don’t ask me. Magic, probably.
Strassen’s Algorithm Analysis
You need to compute 7 recursive calls of half the
size plus O(n2) extra work.
Master Theorem: a = 7, b = 2, d = 2.
a > bd. O(nC) with C = log27 ≈ 2.807…
Improvement for very large matrices.
Best known algorithm: O(n2.376…) very
impractical.