CSE 421 Assignment #4
Autumn 2008

Due: Friday, October 24, 2008.

Reading Assignment: Kleinberg and Tardos Chapter 5, Section 13.5, and Sections 6.1-6.2.

Problems: Re-read the Grading Guidelines before answering

  1. Kleinberg and Tardos, Chapter 5, Problem 1, page 246

  2. Kleinberg and Tardos, Chapter 5, Problem 5, page 248

  3. Solve each of the following recurrences to get the best asymptotic bounds you can on T(n) in each case using O( ) notation. You can assume that everything is rounded down to the nearest integer.

    1. T(n)= T(n/(4log2 n))+ 2n for n > 1 and T(1)=1.

    2. T(n)= n1/2 T(n1/2) +13n1/2 for n > 1 and T(1)=1.

    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.

  4. Modify Karatsuba's algorithm based on splitting the polynomials into 3 pieces instead of two. Base your algorithm on a method for multiplying two degree 2 polynomials that uses 6 multiplications. What is the running time of this algforithm? How does the running time of your new algorithm compare to that of Karatsuba's algorithm?

  5. Extra credit: Show how to multiply two degree 2 polynomials using only 5 multiplications. If you use this in a modified version of Karatsuba's algorithmi what running time would you get?
    HINT: Use evaluation and interpolation at 5 points.

  6. Extra credit (due by Oct 31, 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. 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.