CSCI 3650
Spring 2015
Homework Assignment 2

  1. From the book: 4-1(a-d)[page 107].

  2. From the book: 4-5(a-c)[page 109].

  3. 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 mn. 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.)