CSE 421 Assignment #4
Autumn 2012

Due: Friday, October 26, 2012.

Reading Assignment: Kleinberg and Tardos Chapter 6, sections 6.1-6.3.

Problems: (see the Grading Guidelines before answering)

1. Kleinberg and Tardos, Chapter 5, Problem 3, pages 246-247.

2. Kleinberg and Tardos, Chapter 5, Problem 7, pages 248-249.

3. Kleinberg and Tardos, Chapter 6, Problem 2, pages 313-314.

4. Extra credit: Show how to multiply two degree 2 polynomials using fewer multiplications of coefficients than the naive algorithm. You can do it with only 5 multiplications. (For partial credit, show how to do this with only 6 multiplications.) Use this to describe an algorithm for polynomial multiplication that is more efficient than Karatsudba's algorithm. Why wouldn't 6 multipications be enough to be better than Karatsuba's algorothm? HINT: Use evaluation and interpolation.

5. From Homework 3, due on Oct 26 in conjunction with homework 4. (May be done with a partner - list your partner on your homework.) In describing and analyzing Strassen's algorithm we assumed that we used divide and conquer all the way down to tiny matrices. However, on small matrices the ordinary matrix multiplication algorithm will be faster because of lower overhead. This is a common issue with divide and conquer algorithms. The best way to run these algorithms typically is to test the input size n at the start to see if it is big enough to make using divide and conquer worthwhile; if n is larger than some threshold t then the algorithm would do a level of recursion, if n is below that threshold then it would do the non-recursive algorithm.

   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=2ⁱ 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.

6. (Extra Credit)