Non-Programming Exercises:

1. This problem has to do with multiplying 3-by-3 matrices.
   1. How many multiplications does it take to multiply 3-by-3 matrices in the usual way?
   2. Suppose you could multiply 3-by-3 matrices using 25 multiplications. What result would this give for asymptotic multiplication of matrices using Strassen's general approach?
   3. Suppose we keep multiplying 3-by-3 matrices using fewer and fewer multiplications. At what point would Strassen's approach give us a better asymptotic result than the result for 2-by-2 matrices:
      Big-Theta(n^k), where k = log₂(7) = 2.807...?

2. In the lecture material for February 10: Feb 10 under items IX. 2. a.- e. are 5 recurrences to which the master theorem applies. In each case work out the values of a, b, and d, and say what the Big-Theta performance is according to the Master Theorem.

3. In the context of the program that gives a binary search tree of strings: Java, write a recursive function height that will give the maximum number of levels in the tree. You can just write pseudo-code, or you can debug your function if you wish. [Hint: the height of a single-node tree is 0. The height of any tree is given by
   max(height of left subtree, height of right subtree) + 1.]

   Here is an answer: height example.