CSC 505 Homework #1 Problem 6 complete solution correct answer key

CSC 505 Homework #1 Problem 6 complete solution correct answer key

6. [worth 5 points] Applying analysis of divide and conquer to a concrete problem.
The dominant operations in Strassen's matrix multiplication algorithm, particularly if the numbers being manipulated are multiple precision (take up more than one machine word), are scalar multiplications and scalar additions.
Recurrences for these two operations are as follows.
M(n) = 7M(n=2) note: no scalar multiplications are done before or after any recursive calls
M(1) = 1
for scalar multiplications
A(n) = 7A(n=2) + 10(n=2)2 there are 10 additions of n=2 n=2 matrices
A(1) = 0
for scalar additions
Strassen's algorithm, even if you ignore bookkeeping overhead, is not a good choice for small matrices.
Your job is to gure out the exact value of n at which it makes sense to stop recursing and use the ordinary matrix multiplication algorithm instead. The number of scalar operations for the ordinary algorithm are n3 multiplications and n3 additions (actually there are n3 􀀀 n2 but let's not make things too complicated). To simplify your calculations, assume that multiplication takes twice as long as addition.
You should express the answer as simply as possible (you may want to assume s is a power of 2 to start with and come up with a more exact value later; this is not exactly kosher, but it works). Do not convert logarithms into numbers, i.e., say lg 7 instead of 2:80735492206 or 2:81.
Rather than come up with a closed form solution for s you can leave it as nding the root of a polynomial (one of the terms will be a non-integer power). You should then use a sophisticated calculator, MatLab, or any program that works to interpolate (using, e.g., binary search or Newton's method) an exact value for s. The result should be rounded up to the next power of 2.
3 points for coming up with the right recurrences with a base case that is not 1 and evaluating them;
2 points for the remaining details.
For up to 10 points extra credit, do an experiment to determine the best value for n at which to stop the recursion.
You can get up to 3 points for a detailed description of how such an experiment should be conducted. Submit your description, a writeup of your experiment, and your code with instructions for compiling and running it on a Unix-based system to the h1ex locker. It should be a zip archive with the name h1ex uid.zip, where uid is your unity login id.