Non-Programming Exercises:

1. Prove using mathamatical induction that T(n) = 2*(n³) - (n²) satisfies the recurrence for T(n) given at the beginning of the write-up:

   
           T(1) = 1
           T(n) = 8*T(n/2) + 4*(n/2)2, for n > 1.
   

2. Text, page 146-147, Exercises Set 4.5: Problem 3, both a. and b. [This has to do with integer multiplication, but you can still answer the questions.]

3. This question has to do with Strassen's matrix multiplication algorithm.
   1. Suppose one bases the calculations on 18 additions and subtractions needed to multiply 2-by-2 matrices instead of the 15 that the write-up used. (Of course still using 7 multiplications instead of 8.) See how this changes the formula for the exact total number of operations needed for the n-by-n case (where n is a power of 2).
   2. What would the answer be like if one needed 30 additions and subtractions, in addition to 7 multiplications.

4. Text, page 146-147, Exercises Set 4.5: Extended Problem 9. In 1978, V. Pan found a way to multiply matices of the following sizes, in the number of multiplications given:

   Size	Multiplications
   68-by-68	132,464
   70-by-70	143,640
   72-by-72	155,424

   In each of the three cases, say what asymptotic performance this give for matrix multiplication? Which one is the best? Are all three of these better than the asymptotic performance of Strassen's algorithm? [This is fairly tricky. You'll have to think carefully about it. You would naturally imagine that this is an improvement over Strassen's result.]

5. Suppose a + bi and c + di are two complex numbers, where a, b, c, and d are floating point numbers, and i is the square root of -1. The product of these two numbers is the number x + yi = (a*c - b*d) + (a*d + b*c)i. This requires 4 mulitplications of floating point numbers.
   1. Show how you can get the same result using only 3 multiplications. [Hint: Use the trick on page 143 for multiplying two decimal numbers.]
   2. Illustrate this with the specific numbers 3 + 7i and 5 + 2i.

6. This problem deals with the quicksort algorithm in the text on pages 128-132.
   1. Implement this algorithm almost exactly as it is presented in the text (except translated into Java/C/C++, so that in particular, you would replace repeat-until with do-while). However, you should use one of the strategies from the class to make this algorithm randomized. (Either randomize the array initially, or choose a random pivot, but of course not both.) [Note: You must use the algorithm from the text, and you may not just grab some quicksort implementation off the Internet.]
   2. As with Assignment 3, arrange to count the number of comparisons (where this means actually comparing array elements, as in A[i] >= p, but not index comparisons, as in i >= j). Again as before, use a random number generator to create a random array of ints or doubles for sorting. Use n, the size of the array as an input parameter, and let the number of comparisons be the output. Try this for  n = 10, 100, 1000, 10000, 100000, 1000000, ... (until it takes too much time on your computer). Let c(n) be the number of comparisons. In each case, print the numbers n, c(n), c(n)/(n*log₂n) (as a double).