Reading Assignment: Kleinberg and Tardos Chapter 5, Section 13.5.
Problems: (see the Grading Guidelines before answering)
Your job in this question is to figure out the best choice for that threshold value for a version of Strassen's algorithm over the integers based on your implementation. (See the class slides for the description of the recursion used in Strassen's algorithm and for the code for the basic non-recursive algorithm for matrix multiplication.)
You should code up the pure algorithms first and then create the final hybrid algorithm. For simplicity you can assume that the size n of the matrix is a power of 2 and figure out the matrix size t=2i below which it is better to switch to the ordinary algorithm.
The language you choose to implement this in is somewhat up to you. However, the object-oriented implementation of two-dimensional arrays in Java with most of its standard class libraries is terrible for working with two-dimensional sub-arrays. Use a language such as C that makes such operations easy and efficient. For your solution print out your code, the timings that you found, and the choice of t that you found works best.