The data structures in the above exercise are inefficient for sparse
polynomials because zeros are represented explicitly. E.g. consider
the polynomial . Represented as a Maple list it would be
[10,0,0,0,0,0,0,0,1,1]
and as a linked list it is
[10,[0,[0,[0,[0,[0,[0,[0,[0,[1,[1,NIL]]]]]]]]]]].
A more efficient representation for sparse polynomials is to store
just the non-zero terms. Let us store the 'th non-zero
term
as
where
.
Now write procedures to add and multiply sparse univariate polynomials
which are represented as