CSE 421 Assignment #3
Autumn 2012

Due: Friday, October 19, 2012.

Reading Assignment: Kleinberg and Tardos Chapter 5, Section 13.5.

Problems: (see the Grading Guidelines before answering)

1. Kleinberg and Tardos, Chapter 4, Problem 17, page 197.

2. Kleinberg and Tardos, Chapter 4, Problem 19, pages 198-199.

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

4. 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.

5. (Extra Credit) Use the same ideas as used to solve the problem for closest pair in the plane to create an O(n log² n) algorithm for finding closest pairs in 3 dimensions and prove its running time. (This is not optimal; an O(n log n) algorithm exists that uses ideas of the above algorithm plus more flexibility in choosing how to split the points into subproblems so that the difficult strip in the middle has fewer points.)