Due: Wednesday, January 23 at the beginning of class.
From the book: 2.2-1 [page 29] Express the function n3/1000 − 100n2 − 100n + 3 in simple terms using Θ-notation.
From the book: A.1-1 [page 1149] Find a simple formula for ∑nk=1(2k−1).
From the book: A.1-3 [page 1149] Show that ∑∞k=1(k2xk) = x(1+x)/(1−x)3 for 0 < |x| < 1.
From the book: 4.3-1 [page 87].
From the book: 4.3-2 [page 87].
From the book: 4-1(a-d)[page 107].
From the book: 4-5(a-c)[page 109].
For simplicity in typesetting, I will use 0.59 as a stand-in for (log2(3) − 1), since that is its approximate value.
Suppose that m ≤ n. The standard (grade school) algorithm for integer multiplication multiplies an n digit number by an m digit number in time O(nm).
To use the divide-and-conquer algorithm on numbers of unequal size, we can just pad out the smaller number to the same number of digits as the larger number by adding leading 0's. Then the divide-and-conquer algorithm would take time O(n1.59), independent of the smaller value m.
Explain how to hybridize the grade school algorithm and the divide-and-conquer algorithm to get an algorithm that multiplies an n digit number by an m digit number in time (with m < n) O(n m0.59). Explain your algorithm clearly and show that it has the desired time bound. (Hint. Keep it simple! You do not need to modify the divide-and-conquer algorithm. Just use it.)