Announcements
Announcements
Homework 2 due today
Homework 3 online soon
Last Time
Divide and Conquer (Ch 2)
Break problem into pieces
Solve pieces recursively
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
P1 ← Product(A,C)
P2 ← Product(B,D)
P3 ← Product(A+B,C+D)
Return P1X2 + [P3-P1-P2]X + P3
P1 ← KaratsubaMult(A,C)
P2 ← KaratsubaMult(B,D)
P3 ← 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:
Break problem into pieces.
Compute AC, BD, (A+B)(C+D)
Recursively solve pieces.
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? O(n) O(n log(n) O(n2) O(n2 log(n)) 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(n3).
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.