CSE 521, Homework 1

Due 10:30 AM, Wedneday, April 8

Read chapters 1-16, (pages 1-328). I will be assuming that you have seen most of the stuff in the first 15 chapters.

Problem 1. Implement Strassen's algorithm and the naive matrix multiplication algorithm. Where is the cross over point where Strassen's algorithm becomes superior? Suppose you implement Strassen's algorithm so that the naive algorithm is used for small matrices (determine the what small is) - how does this change the cross over point.

You may implement this in whatever language you want -- just make sure the comparison between the algorithms is fair.

Problem 2. Page 37, Exercise 2.2-5 and Exercise 2.2-6.

Problem 3. Page 72, Exercise 4-1 a, c, e, h and Exercise 4-4 a, c, f.

Problem 4. Page 133, Problem 6-1.

Problem 5. Page 169, Problem 8-3.

Problem 6. Page 193, Problem 10-2.

Problem 7. Page 744, Exercise 31.2-4.