Matrix Multiplication $(10$ points$)$

The pseudocode below describes a divide and conquer recursive algorithm to compute the

product of two $nn$ matrices, A and $B.$ For this problem it is not necessary to understand the

$\frac{}{2}$

Matrix$-$Multiply$-$Recursive$(\}$A$,$B$,$C$,$n

if n$==1$

$//$ Base cas

c

$//$ Divide.

partition A$,$B$,$ and C into n$/2\backslash$timesn$/2$ submatrices

A

$//$ Conquer.

Matrix$-$Multiply$-$RecurSive$(\}\backslash$mp@subsup$\{$A$\}\{11\}\{\},\backslash$mp@subsup$\{$B$\}\{11\}\{\},\backslash$mp@subsup$\{$C$\}\{11\}\{\},$n$/2$

MatriX$-$MultTPLY$-$RECURSIVE $(\}\backslash$mp@subsup$\{$A$\}\{11\}\{\},\backslash$mp@subsup$\{$B$\}\{12\}\{\},\backslash$mp@subsup$\{$C$\}\{12\}\{\},$n$/2$

MATRIX$-$MULTIPLY$-$RECURSIVE $(\}\backslash$mp@subsup$\{$A$\}\{21\}\{\},\backslash$mp@subsup$\{$B$\}\{12\}\{\},\backslash$mp@subsup$\{$C$\}\{22\}\{\},$n$/2$

Matrix$-$Multiply$-$Recursive$(\}\backslash$mp@subsup$\{$A$\}\{12\}\{\},\backslash$mp@subsup$\{$B$\}\{21\}\{\},\backslash$mp@subsup$\{$C$\}\{11\}\{\},$n$/2$

Matrix$-$Multiply$-$Recursive$(\}\backslash$mp@subsup$\{$A$\}\{12\}\{\},\backslash$mp@subsup$\{$B$\}\{22\}\{\},\backslash$mp@subsup$\{$C$\}\{12\}\{\},$n$/2$

Matrix$-$MultIply$-$ReCursive $(\}\backslash$mp@subsup$\{$A$\}\{22\}\{\},\backslash$mp@subsup$\{$B$\}\{21\}\{\},\backslash$mp@subsup$\{$C$\}\{21\}\{\},$n$/2$

MatriX$-$MultIPlY$-$RECURsive$(\}\backslash$mp@subsup$\{$A$\}\{22\}\{\},\backslash$mp@subsup$\{$B$\}\{22\}\{\},\backslash$mp@subsup$\{$C$\}\{22\}\{\},$n$/2$

$($a$)$ Write the recurrence equation for the running time of MATRIX$-$MULTIPLY$-$RECURSIVE

based on the pseudocode. $(5$ points$)$

$T(n)=$

$($b$)$ Use the master theorem for solving recurrences to find an asymptotic tight bound for

MATRIX$-$MULTIPLY$-$RECURSIVE. State the values for $a,b,$ and $f(n),$ and show which case of

the master theorem you are using. $(5$ points$)$

$a=$

$b=$

$f(n)=$

Master Theorem Case $\frac{?}{?}$#:

For the following recurrence equation draw a recursion tree of at least $3$ levels, compute the

total work done for an input size $n$ by adding all nodes in the entire tree, and then state an

asymptotic tight bound for the recurrence $(10$ points$)$

$T(n)=2T(\frac{n}{4})+n^3$

Use any method you would like to compute asymptotic tight bounds for the following

recurrences. It is not necessary to show any work. $(10$ points$)$

$($a$)T(n)=2T(\frac{n}{2})+n^3$

$($b$)T(n)=T(\frac{8n}{11})+n$

$($c$)T(n)=16T(\frac{n}{4})+n^2$

$($d$)T(n)=4T(\frac{n}{2})+n^{2}log(n)$

$($e$)T(n)=10T(\frac{n}{3})+n^2$

True or False? $(5$ points$)$

$($a$)$ Divide and conquer recursive algorithms are always more

efficient then their iterative counterparts.

$($b$)$ For very large input sizes, merge sort is generally more efficient

than insertion sort.

$($c$)$ Recursive algorithms use for loops to compute

solutions to subproblems.

$($d$)$ The master theorem for solving recurrences can be used to

solve any recurrence equation.

$($e$)T(n)=T(\frac{n}{2})+(1)$ is $(1)$