CSCI 6410
Fall 2011
Assignment 3

Due: Wednesday, Sep. 28.

1. Give a solution, in big-Θ form, for each of the following recurrences.

   1. T(n) = 2T(n/2) + Θ(n²)
   2. T(n) = 3T(n/2) + Θ(n²)
   3. T(n) = 4T(n/2) + Θ(n²)
   4. T(n) = 5T(n/2) + Θ(n²)
   5. T(n) = T(n/3) + Θ(n)
   6. T(n) = 3T(n/3) + Θ(n)

2. Recursion can be seen as an amplifier. The book describes Strassen's algorithm for matrix multiplication (page 79 in the third edition, page 735 in the second edition, page 739 in the first edition). It is a divide-and-conquer algorithm. What does recursion amplify that makes Strassen's algorithm efficient on very large matrices? Explain the key idea without writing down the details.

3. Solve all parts, a-c, of the Chip Testing problem from the book. It is problem 4-5 on page 109 in version 3, problem 4-6 on page 87 in version 2 and problem 4-7 on page 75 in version 1.