Cashback Offer from 10th to 18th September 2021. Get Flat 10% Cashback credited to your account for a minimum transaction of \$80. Post Your Question Today!

Question DetailsNormal
\$ 12.00

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

Question posted by

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
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.

\$ 12.00

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

• This solution is not purchased yet.
• Submitted On 13 Jul, 2015 03:28:35
Strassen’s matrix multiplication: Strassen’s showed that 2x2 matrix multiplications can be accomplished in 7 Multiplications and 18 ...
Buy now to view the complete solution
Other Similar Questions
vpqnr...

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

Strassen’s matrix multiplication: Strassen’s showed that 2x2 matrix multiplications can be accomplished in 7 Multiplications and 18 additions or subtractions. • This reduction can be done by divide and conquer app...
Exper...

### CSC 505 Homework #1 | Problem No.6

Strassen’s matrix multiplication:

Strassen’s showed that 2x2 matrix multiplications can be accomplished in 7 Multiplications and 18 additions or subtractions.

•    T...

#### The benefits of buying study notes from CourseMerit

##### Assurance Of Timely Delivery
We value your patience, and to ensure you always receive your homework help within the promised time, our dedicated team of tutors begins their work as soon as the request arrives.
##### Best Price In The Market
All the services that are available on our page cost only a nominal amount of money. In fact, the prices are lower than the industry standards. You can always expect value for money from us.
##### Uninterrupted 24/7 Support
Our customer support wing remains online 24x7 to provide you seamless assistance. Also, when you post a query or a request here, you can expect an immediate response from our side.

\$ 629.35