CS19002 Programming and Data Structures Laboratory Spring 2010, Section 5

# Assignment 6

A multi-variate polynomial can be represented by a sum of non-zero terms. We need to store the number of terms, and a list of the non-zero terms. For example, consider the following 4-variate polynomial, where the variables are denoted by a,b,c,d.

```   5a2bd3 - 2d5 + abcd + 31
```

A possible representation of this polynomial is shown below.
 Number of terms 4 Term 0 5 2 1 0 3 Term 1 -2 0 0 0 5 Term 2 1 1 1 1 1 Term 3 31 0 0 0 0

In order to implement this storage of a multi-variate polynomial, we use the following C structure.

```   #define NVAR 5
#define MAX_TERM 1000

typedef struct {
int nterm;
int term[MAX_TERM][1+NVAR];
} mvpoly;
```

I supply a function to print a multi-variate polynomial in the above storage format.

```   void polyprint ( mvpoly f )
{
int i, k;

for (i=0; i<f.nterm; ++i) {
if ((i)&&(f.term[i][0]>=0)) printf("+");
if (f.term[i][0] != 1) printf("%d", f.term[i][0]);
for (k=1; k<=NVAR; ++k) {
if (f.term[i][k]) printf("%c",'a'+(char)(k-1));
if (f.term[i][k]>1) printf("^%d", f.term[i][k]);
}
}
}
```

Henceforth, we will assume that n is the number of variables.

### Part 1: An initialization function

Write a function in order to return the polynomial

`   a + b + c + ... (n variables)`

The function should have the following prototype:

`   mvpoly setpoly ();`

### Part 2: The product function

Write a function to compute the product of two multi-variate polynomials. Your function should have the following prototype.
`   mvpoly polyprod ( mvpoly f, mvpoly g );`

Note that when you multiply two multi-variate polynomials, the same product monomial may appear more than once during the monomial-by-monomial product of the input polynomials. It is, therefore, necessary to collect similar terms in the output polynomial. For example, the product of a+b and a+2b should be computed as a2+3ab+2b2 instead of as a2+2ab+ab+2b2.

### Part 3: The main() function

Use n = 5 variables a,b,c,d,e. Compute and print the polynomials (a+b+c+d+e)i for i = 1,2,3,4,5.

### Sample output

Here is a possible output for n = 3.

```   (a+b+c)^1 = a+b+c

(a+b+c)^2 = a^2+2ab+2ac+b^2+2bc+c^2

(a+b+c)^3 = a^3+3a^2b+3a^2c+3ab^2+6abc+3ac^2+b^3+3b^2c+3bc^2+c^3
```