<aside> 💡
Topic: Divide-and-Conquer and Strassen’s matrix multiplication algorithm
Deadline:
Team members:
</aside>
此作業沒有程式題，都交紙本。
Let $A=\begin{bmatrix}1 & 2 & 3\\4 & 5 & 6\\7&8&9 \end{bmatrix}$ and $B=\begin{bmatrix}8 & 9 & 5\\7 & 3 & 2\\4&6&1 \end{bmatrix}$. Use Strassen’s method to compute $A\cdot B$ with threshold =2. (5pts)
Consider algorithm solve given below. This algorithm solves problem $P$ by finding the output (solution) $O$ corresponding to any input $I$.
<aside> 💡
void solve (input $I$, output& $O$) {
if (size($I$)==1)
find solution $O$ directly;
else{
partition $I$ into 5 inputs $I_1$, $I_2$, $I_3$, $I_4$, $I_5$, where
size($I_j$)=size($I$)/3 for $j=1,\cdots, 5$;
for ($j=1; j<=5; j++$)
solve($I_j, O_j$);
Combine $O_1, O_2, O_3, O_4, O_5$ to get $O$ for $P$ with input $I$;
}
}
</aside>
Assume $g(n)$ basic operations for partitioning and combing and no basic operations for an instance of size $1$.
(a) Write a recurrence equation $T(n)$ for the number of basic operations needed to solve $P$ when the input size is $n$.
(b) What is the solution to this recurrence equation if $g(n)\in \Theta(n)$?
(c) Assuming that $g(n)=n^2$, solve the recurrence equation exactly for $n=27$.
(d) Find the general solution for $n$ a power of $3$ for general $g(n)$.
(2pts each)
Find the asymptotic tight bound of $T(n)$. (Use Master’s theorem. If it is not applicable, find other method. ) (3pts each)