---

CIS 3223 Lab04 and Lab05 – Implementation of Polynomial Multiplication using Divide-and-Conquer Approach

DUE: (10:30am Friday, Feb 29, 2008)

---

TASKS

1. (20%) Write the pseudocode for the Multiplication of the Polynomials using Divide-and-Conquer Approach covered in class. Inputs are two arrays, p and q, both of length N+1, representing the polynomial coefficients (i.e. the polynomials are of degree N). The output is an array r of length 2N+1. Propose how the algorithm should be used when the polynomials are of different degrees.

2. (20%) Implement in Matlab the algorithm for straightforward polynomial multiplication covered in class. This algorithm will be useful in testing the correctness of the divide-and-conquer solution. You should do it by writing the function:

r = multiply_poly_test(p, q)

that takes arrays p and q of length N as input and produces r as output. Submit the Matlab code you wrote.

3. (40%) Implement the algorithm in Matlab. You should do it by writing the function:

r = multiply_poly(p, q)

that takes arrays p and q of length N as input and produces r as output. Submit the Matlab code you wrote. Test the correctness of the algorithm by generating random polynomials of length N and comparing solutions by multiply_poly_test and multiply_poly.

4. (20%) Test the runtime of both algorithms on polynomials of degree N = 10, 100, 1000, 10000 whose coefficients are randomly generated. List the actual runtimes for each N.