DS: polynomial addition - 1

Polynomial:

A polynomial is sum of terms where each term has a form:

a x^e

where a = coefficient

x= variable

e=exponent

ADT:

concider a polynomial a(x)=25x⁶ +10x⁵ +6x² +9

* LeadExp(a)=6 // 6 is leading/largest exponent of polynomial

* Coeff(a,LeadExp(a))=25 // 25 is coefficient with respect to leading exponent

* IsZero(a) //returns FALSE since polynomial a exists

*Attach(a,15,3) // Attach 15x³ to polynomial a

a(x)=25x⁶ +10x⁵ +6x² +9 + 15x³

*Remove(a,6) // polynomial obtained after removing 25x⁶

a(x)=10x⁵ +6x² +9 + 15x³

Design an algorithm to add two polynomials using ADT polynomial

c=a+b;

where

• a is the first polynomial
• b is second polynomial
• c is the polynomial obtained after adding polynomial a and b

Case1: power of two terms to be added are equal.

a(x)=25x⁶ +10x⁵ +6x² +9

b(x)=15x⁶ +5x⁴ +4x³

c=40x⁶

Since LeadExp(a) is equal to LeadExp(b), we add the coefficient of a with coefficient of b using the statement

sum=Coeff(a,LeadExp(a))+Coeff(b,LeadExp(b)) //sum=25+15=40

to get 40x⁶ and insert the result 40x⁶ into polynomial c. This can be done using the statement:

if(sum!=0) Attach(c,sum,LeadExp(a)); //c=40x⁶

Now we move on to next term of polynomial a and b by removing the added terms by calling the function Remove() as shown below:

a=Remove(a, LeadExp(a));

b=Remove(b, LeadExp(b));

and the following polynomials a and b are returned:

a(x)=10x⁵ +6x² +9

b(x)=5x⁴ +4x³

Now the complete code can be written as:

if(LeadExp(a)==LeadExp(b))

{

sum=Coeff(a,LeadExp(a))+Coeff(b,LeadExp(b));

if(sum!=0) Attach(c,sum,LeadExp(a));

a=Remove(a, LeadExp(a));

b=Remove(b, LeadExp(b));

}

Case2: Power of first term of polynomial a is greater than power of first term of polynomial b.

a(x)=10x⁵ +6x² +9

b(x)=5x⁴ +4x³

c=10x⁵

Since LeadExp(a) is greater than LeadExp(b), we insert the term of a into c.

Attach(c,Coeff(a,LeadExp(a)),LeadExp(a));

Now we remove the next term of polynomial a by calling the function Remove() as shown below:

a=Remove(a, LeadExp(a));

And the following polynomial a is returned

a(x)=6x² +9

b(x)=5x⁴ +4x³

Now, the complete code can be written as shown below:

if(LeadExp(a)>LeadExp(b))

{

Attach(c,Coeff(a,LeadExp(a)),LeadExp(a));

a=Remove(a, LeadExp(a));

}

Case Default:

if(LeadExp(a)<LeadExp(b))

{

Attach(c,Coeff(a,LeadExp(b)),LeadExp(b));

b=Remove(b, LeadExp(b));

}

Function to add two polynomials a and b

c=Zero();

while(IsZero(a)==FALSE&& IsZero(b)==FALSE)

{

if(LeadExp(a)==LeadExp(b))

{

sum=Coeff(a,LeadExp(a))+Coeff(b,LeadExp(b));

if(sum!=0) Attach(c,sum,LeadExp(a));

a=Remove(a, LeadExp(a));

b=Remove(b, LeadExp(b));

}

else if(LeadExp(a)>LeadExp(b))

{

Attach(c,Coeff(a,LeadExp(a)),LeadExp(a));

a=Remove(a, LeadExp(a));

}

else(LeadExp(a)<LeadExp(b))

{

Attach(c,Coeff(a,LeadExp(b)),LeadExp(b));

b=Remove(b, LeadExp(b));

}

}

-------------------------------------------------------------------------