CSCE 411 Lecture 6

Lecture Slides

« previous | Friday, September 7, 2012 | next »

Master Theorem

$T(n)=aT\left({\frac {n}{b}}\right)+f(n)$

We assume $a\geq 1$, $b>1$, and $f(n)$ eventually positive

1. $f(n)=O(n^{\log _{b}{a}-\epsilon })\longrightarrow T(n)=\Theta (n^{\log _{b}{a}})$
2. $f(n)=\Theta (n^{\log _{b}{a}})\longrightarrow T(n)=\Theta (n^{\log _{b}{a}}\log {n})$
3. $f(n)=\Omega (n^{\log _{b}{a}+\epsilon })\longrightarrow T(n)=\Theta (f(n))$

Note: For case 3, $f(n)$ must be regular

Matrix Multiplication

Classic algorithm

$AB=\left(\sum {j=1}^{n}a_{ij}\,b_{jk}\right)$ for $1\leq (i,j,k)\leq n$

for i from 1 to n do:

 for j from 1 to k do:
   for t from 1 to m do:

   end for
 end for

end for

Approx $\Theta (n^{3})$

Divide and Conquer

${\begin{bmatrix}A_{0}&A_{1}\\A_{2}&A_{3}\end{bmatrix}}\times {\begin{bmatrix}B_{0}&B_{1}\\B_{2}&B_{3}\end{bmatrix}}={\begin{bmatrix}A_{0}\times B_{0}+A_{1}\times B_{2}&A_{0}\times B_{1}+A_{1}\times B_{3}\\A_{2}\times B_{0}+A_{3}\times B_{2}&A_{2}\times B_{1}+A_{3}\times B_{3}\end{bmatrix}}$

Divide batrices $A$ and $B$ into four smaller matrices:

• 8 matrix multiplications on submatrices of $A$ and $B$
• $\Theta (n^{2})$ scalar additions

Running Time

• $T(n)=8T\left({\frac {n}{2}}\right)+\Theta {n^{2}}$
• $T(2)=\Theta (1)$
• $T(n)\in \Theta (n^{3})$ great, all that work for nothing.

Can we do fewer operations?

Strassen's Matrix

Just calculate 7 products and do a bunch of cheap additions

$T(n)=7T\left({\frac {n}{2}}\right)+\Theta (n^{2})\in O(n^{2.807})$

Integer Multiplication

Elementary school algorithm $41\times 42=101001_{2}\times 101010_{2}=1010100_{2}+101010000_{2}+10101000000_{2}=11010111010_{2}=1722_{10}$

Multiplication of 2 $n$-bit numbers takes $\Omega (n^{2})$.

Kolmogrov (at one of his seminars) conjectured that we can't do better, but Karatsuba proved him wrong a week later.

Dividery and Conquery

Split $x$ and $y$ into two smaller parts: their most significant and least significant parts:

• $x=2^{\frac {n}{2}}\,A+B$, where $A$ and $B$ are n/2-bit algorithms
• $x=2^{\frac {n}{2}}\,C+D$, where $C$ and $D$ are n/2-bit algorithms
• $xy=2^{n}AC+2^{\frac {n}{2}}BC+2^{\frac {n}{2}}AD+BD$ still $T(n)=4T\left({\frac {n}{2}}\right)+\Theta (n)=\Theta (n^{2})$

What if we multiply $(A+B)(C+D)=AC+AD+BC+BD$? Just correct the terms:

$xy=(2^{n}-2^{\frac {n}{2}})AC+2^{\frac {n}{2}}(A+B)(C+D)+(1-2^{\frac {n}{2}})BD$

This has only 3 multiplications, so $T(n)=3\left({\frac {n}{2}}\right)+\Theta (n)=\Theta (n^{\log _{2}{3}})$

Summary of Dividery and Conquery

1. Split $x$ into two parts $A$ and $B$
2. Split $y$ into two parts $C$ and $D$
3. calculate $AC$, $(A+B)(C+D)$, and $BD$
4. shift each of the results by a certain amount and add all of those together