a. Show how to multiply two linear polynomials ax + b and cx + d using only three multiplications. One of the multiplications is (a + b) · (c + d).

b. Give two divide-and-conquer algorithms for multiplying two polynomials of degree-bound n in Θ(n ^{lg 3}) time. The first algorithm should divide the input polynomial coefficients into a high half and a low half, and the second algorithm should divide them according to whether their index is odd or even.

c. Show how to multiply two n-bit integers in O(n ^{lg 3}) steps, where each step operates on at most a constant number of 1-bit values.