COSC: Data Structures and Algorithms Problem: You will implement and test a prel
ID: 668949 • Letter: C
Question
COSC: Data Structures and Algorithms
Problem:
You will implement and test a preliminary version of the polynomial class, using a small array to store the coefficients of the polynomial in order of increasing exponents, following the design pattern of object-oriented approach. Suppose the range of the exponents is in [0, 30).
Use an array as a private member variable.
insert(), adding a new term on specific exponent.
remove(), deleting a term.
Have a add() method, deciding the parameters and the return value by yourself.
Have a sub() method, deciding the parameters and the return value by yourself.
A printout() method to display the polynomial expression.
And other variables, or methods if needed.
Do the algorithm analysis on the implemented method, and give the big O notation estimation.
You will also need to write a PolynomialTest program to initialize two linear polynomial objects and apply the operation on it and also display the result. For example, P1=x + 3x5 - 5x8; P2= 2x3 - 4x5+ 2x7; So P3= P1+P2= x +2x3 - x5+ 2x7 - 5x8, P4 = P1-P2 = x - 2x3 + 7x5- 2x7 - 5x8.
Explanation / Answer
class Polynomial:
public class Polynomial
{
int coeff[] = new int[30];
int maxExp = 0;
public Polynomial()
{
for(int i=0;i<coeff.length;i++)
coeff[i] = 0;
}
public void insert(int exponent,int value)
{
coeff[exponent] = value;
if(exponent > maxExp)maxExp = exponent;
}
public void delete(int exponent)
{
coeff[exponent] = 0;
int temp = maxExp;
for(int i=maxExp;i>=0;i--)
{
if(coeff[i] != 0)
{
maxExp = i;
break;
}
}
if(maxExp == temp)
{
maxExp = 0;
}
}
public Polynomial add(Polynomial p1)
{
Polynomial p3 = new Polynomial();
int max = this.maxExp>p1.maxExp?this.maxExp:p1.maxExp;
for(int i=0;i<=max;i++)
{
p3.coeff[i] = this.coeff[i]+ p1.coeff[i];
}
p3.maxExp = max;
return p3;
}
public Polynomial sub(Polynomial p1)
{
Polynomial p3 = new Polynomial();
int max = this.maxExp>p1.maxExp?this.maxExp:p1.maxExp;
for(int i=0;i<=max;i++)
{
p3.coeff[i] = this.coeff[i] - p1.coeff[i];
}
p3.maxExp = max;
return p3;
}
public String toString()
{
StringBuffer sb = new StringBuffer();
for(int i=0;i<=maxExp;i++)
{
if(coeff[i]!=0)
{
if(coeff[i]>0)sb.append("+");
sb.append(coeff[i]+"x"+i+" ");
}
}
return sb.toString();
}
}
//#########################################################################################
Class PolynomialTest:
public class PolynomialTest {
public static void main(String[] args) {
Polynomial p1 = new Polynomial();
p1.insert(1, 1);
p1.insert(5, 3);
p1.insert(8, -5);
System.out.println(p1);
Polynomial p2 = new Polynomial();
p2.insert(3, 2);
p2.insert(5, -4);
p2.insert(7, 2);
System.out.println(p2);
Polynomial p3 = p1.add(p2);
System.out.println(p3);
Polynomial p4 = p1.sub(p2);
System.out.println(p4);
}
}