Solve the recurrences below using the master theorem if possible, showing your work. One of these is not solvable by the basic master theorem (as stated on page 94 of the textbook) – for that one, explain why we can’t use the master theorem.
\(T(n)=4T(n/2)+n\)
\(T(n)=3T(n/3)+n\)
\(T(n)=4T(n/2)+n^2\lg n\)
\(T(n)=10T(n/3)+n^3\lg n\)
This problem deals with matrix multiplication, and in particular Strassen’s algorithm for matrix multiplication which is discussed in Section 4.2 of the textbook. While we will talk about Strassen’s algorithm at a high-level in class, all of the details are in the book and should be studied carefully there. Note that this problem is very detail-oriented, and you should double-check your work as you go along. I have given some ideas on how to double-check for various parts below.
First, consider the basic matrix multiplication algorithm below. This is a slight re-write of the Square-Matrix-Multiply algorithm in the book, where I avoid one addition in the calculation of each c[i][j] as compared to the book’s algorithm.
Basic-Matrix-Multiply(A,B) // A and B are n x n matrices
let C be a new n x n matrix
for i = 1 to n
for j = 1 to n
C[i][j] = A[i][1]*B[1][j]
for k = 2 to n
C[i][j] = C[i][j] + A[i][k]*B[k][j]
return CDerive a function \(T_1(n)\) that gives the exact number of floating point operations (sometimes called “flops” - count all additions or multiplications) performed by this algorithm. To double-check you work, your formula should give \(T_1(2)=12\) and \(T_1(3)=45\).
Carefully go through Strassen’s algorithm (pages 80-82 in the textbook), and count how many \((n/2)\times(n/2)\) matrix multiplications and \((n/2)\times(n/2)\) matrix additions there are. Use these counts – where each multiplication is performed recursively and each addition of \((n/2)\times(n/2)\) matrices takes \(\left(n/2\right)^2\) flops – to write out a recurrence equation for \(T_2(n)\) that gives the exact number of flops performed by Strassen’s algorithm when \(n\) is a power of 2. Include a base case in your recurrence. Note that “exactly” means you may not use any asymptotic notation. To double-check your work, you can make sure that you get \(T_2(2)=25\) and \(T_2(4)=247\).
Using repeated substitution (as shown in the previous problem), derive the “pattern after \(k\) substitutions” for your recurrence for \(T_2(n)\).
Find the value of \(k\) that brings this down to a base case of size 1, and then evaluate your formula to get a closed form exact solution for \(T_2(n)\). To double-check this, you can evaluate \(T_2(2)\) and \(T_2(4)\) with the closed-form solution, and verify that both give the same results you found earlier when you were evaluating directly with the recurrence.
Make a small table showing the values of \(T_1(n)\) and \(T_2(n)\) for the following four values of \(n\): 16, 64, 256, and 1024. For which of those values of \(n\) is Strassen’s algorithm faster?
Now consider switching the following algorithm that combines Strassen’s algorithm and the Basic-Matrix-Multiply algorithm: For \(n>8\), perform the recursive divide-and-conquer of Strassen’s algorithm, but when \(n=8\) you switch over to the Basic-Matrix-Multiply algorithm. So for example, give two 32 x 32 matrices, Strassen’s algorithm is used to break that down into 16 x 16 matrix multiplications (and additions), and recursion is used again to break each of those down into 8 x 8 matrix multiplications (and additions). At that point, for each of the 8 x 8 multiplications, the Basic-Matrix-Multiply algorithm is used.
Let \(T_3(n)\) be the number of flops used by this algorithm. For \(n>8\), the recurrence you gave for \(T_2(n)\) still applies, and the “pattern after \(k\) substitutions” is exactly the same as you derived above. However, the base case is different. For the hybrid algorithm the base case for the recurrence is \(T_3(8)=T_1(8)\) since you switch over to the Basic-Matrix-Multiply algorithm.
What value of \(k\) brings you to this base case (size 8)? Use that value to substitute in and get an exact closed-form solution for \(T_3(n)\).
Calculate \(T_3(n)\) for the same four \(n\) values as before: 16, 64, 256, and 1024. For what values of \(n\) is this new, hybrid algorithm the fastest of our 3 algorithms? How many times faster than Basic-Matrix-Multiply is it when \(n=1024\)?