Reading Assignment: Kleinberg and Tardos Chapter 5, Section 13.5, and Sections 6.1-6.2.
Problems: Re-read the Grading Guidelines before answering
Hint: You can't use the Master Theorem for Divide and Conquer recurrences directly since the proof assumed that a and b were constants. Howeover you can look at the way we proved the Master Theorem - figure out the number of subproblems per level and the cost per subproblem. If that starts to look too ugly, maybe you can relate the cost to a similar recurrence that you can analyze using ther Master Theorem.
You should code up the pure algorithms first and then create the final hybrid algorithm. Start with values of n that are powers of 2 and figure out the matrix size t below which it is better to switch to the ordinary algorithm.
There is additional credit if you can determine the right thresholds when n is not a power of two. (In the recursion in Strassen's algorithm we assumed that n was even. If n is odd then to do the recursion interpret the matrix as having an extra row and column of 0's at the end so that the two subproblems will be of size (n+1)/2 and ignore the last row and column of the result to return the answer.)
For your solution print out your code, the timings that you found, and the choice of t that you found works best.