please add code only where its written in the starter code. The main focus is the polynomial class please donot change any methods in the starter code given.

Add code only where instructed, namely in the ADD CODE HERE block. You may add helper methods to the Polynomial class, but you are not allowed to modify any other class except for Task 1. You can use whatever package name you like. However, make sure the package name is the first line of the file, so that the grader code can easily remove it. To learn more about packages, see the Java tutorials.

Introduction: In mathematics, a polynomial is an expression constructed from variables and constants, using the operations of addition, subtraction, multiplication, and constant non-negative integer exponents. For example, 5x 3 4x + 7 is a polynomial. In general, a polynomial can be written = =0 = 0 + 1 + 2 2 + + where the coefficients are real numbers and 0. As explained below, in this assignment, the coefficients and the variables will be integers, represented with the Java BigInteger class. Polynomials are heavily used in computer science and in mathematics and also in many other sciences. They are the basis of many models in physics and chemistry and other natural sciences, as well as in the social sciences such as economics.

Instructions and Starter Code:

We will use a singly linked list data structure to represent polynomials and perform basic operations on them, such as addition and multiplication. Essentially, you will write a Polynomial class that builds upon the functionality of a linked list class. The starter code defines four classes which are as follows:

Polynomial - This class defines a polynomial in one variable with positive integer exponents. Most of your work goes into this function. You should use the methods provided with the linked list class to implement the methods of this class. You will notice that the template we provided use Java BigInteger for storing the polynomial coefficient and variable. We intentionally chose BigInteger over floating point (e.g. double) to avoid numerical issues associated with polynomial evaluation.

SLinkedList This class implements a generic singly linked list. You do not have to implement the functionality of linked list as it is already provided with the starter code. However, you must implement the cloning functionality (Task 1 see below) for performing a deep copy of the list.

Term This is a simple class that represents a single term of a polynomial. Example: 5 2 . This class is also provided with the starter code. You do not have to modify this class, but you are required to understand what it does and how.

DeepCopy This is a small user defined interface for enforcing deep copy functionality. You are not required to understand Java interfaces for completing this assignment as the underlying complexity is handled by the starter code. We will discuss Java interfaces in the lectures a few weeks from now.

Valid polynomial representation: Any method that outputs a polynomial or modifies an existing polynomial (adding a term or multiplying by a term) must ensure that this polynomial satisfies the following: There must be no term in the polynomial with zero coefficient. e.g: term 0 3 is not allowed. The exponents in the list must be in decreasing order Exponents can be non-negative integers only e.g. a term 2 is not allowed. There can be at most one term for each exponent. A polynomial can be zero, i.e. p() = 0. In this case, the polynomial must be an empty linked list with no term. i.e. size of the linked list should be zero.

Methods that you need to implement (100 points total) The methods are listed below. See the starter code for method signatures and more details about what the methods do. Your implementations must be efficient. For each method below, we indicate the worst case run time using O() notation. This worst case may depend on either the order of the polynomial as in the definition above, or it may depend on the number of terms in the polynomial. Note that + 1. 1.

SLinkedList.deepClone (15 points) Returns a deep copy of the linked list object. It should step through the linked list and make a copy of each term. The runtime of this method should be ().

2. Polynomial.addTerm (30 points) Add a new term to the polynomial. Use the methods provided by the SLinkedList class. The runtime of this method should be ().

3. Polynomial.add (10 points) This is a static method that adds two polynomials and returns a new polynomial as result. You may use any of the class methods. Be careful not to modify either of the two polynomials. The runtime of this method should be (1 + 2 ) where 1, 2 are the number of terms in the two polynomials being added.

4. Polynomial.eval (20 points) The polynomial object evaluates itself for a given value of using Horners method. The variable is of BigInteger data type, as mentioned earlier. Horners method greatly speeds up the evaluation for exponents with many terms. It does so by not having to re-compute the fresh for each term. Note that you should not use Term.eval( ) method to evaluate a particular term. That method is provided for you only to help with testing, namely to ensure that your implementation of Horners method is correct. A good resource for understanding Horners method is: https://www.geeksforgeeks.org/horners-method-polynomial-evaluation/ . Alternatively, you may use any other resource explaining Horners method. Note the method described in the above resource works only when a polynomial has all + 1 terms (up to order ). However, your polynomial representation may not have all terms. Hence, you must modify your implementation accordingly. We emphasize that the efficiency of your solution is very important. If a polynomial of order has all + 1 terms, then normal brute force polynomial evaluation would take time O(2 ), that is, if you were to evaluate each term individually and sum the results. Horners algorithm is more efficient, namely it would take time O(). As such, we will evaluate you on polynomials with a very large number of terms that will stress test the O( ) efficiency of your Polynomial.eval method, as well as its correctness. Your algorithm should take time O(). One heads up about terminology: when we discuss the complexity of various operations in this assignment, e.g. on the discussion board, we will use term order in two different ways. One way is to refer to the order the polynomial. Another is to refer to the O( ) complexity, where in general people often say order for big O, that is, people often refer to O(1), O(), O( 2 ) as order 1, , and squared instead of big O of 1, big O of and big O of squared, respectively.

5. Polynomial.multiplyTerm (15 points) This is a private helper method used by the multiply function. The polynomial object multiplies each of its terms by an argument term and updates itself. The runtime of this method should be ().

6. Polynomial.multiply (10 points) This is a static method that multiply two polynomials and returns a new polynomial as result. Careful not to modify either of the two polynomials. We recommend you use Polynomial.multiplyTerm, Polynomial.add and any other helper methods that you need. The runtime of this method should be (12 ) where 1, 2 are the number of terms in the two polynomials being multiplied.

STARTER CODE FOR POLYNOMIAL:

//package assignments2018.a2template;

import java.math.BigInteger;

public class Polynomial

{

private SLinkedList polynomial;

public int size()

{

return polynomial.size();

}

private Polynomial(SLinkedList p)

{

polynomial = p;

}

public Polynomial()

{

polynomial = new SLinkedList();

}

// Returns a deep copy of the object.

public Polynomial deepClone()

{

return new Polynomial(polynomial.deepClone());

}

/*

* TODO: Add new term to the polynomial. Also ensure the polynomial is

* in decreasing order of exponent.

*/

public void addTerm(Term t)

{

/**** ADD CODE HERE ****/

// Hint: Notice that the function SLinkedList.get(index) method is O(n),

// so if this method were to call the get(index)

// method n times then the method would be O(n^2).

// Instead, use a Java enhanced for loop to iterate through

// the terms of an SLinkedList.

/*

for (Term currentTerm: polynomial)

{

// The for loop iterates over each term in the polynomial!!

// Example: System.out.println(currentTerm.getExponent()) should print the exponents of each term in the polynomial when it is not empty.

}

*/

}

public Term getTerm(int index)

{

return polynomial.get(index);

}

//TODO: Add two polynomial without modifying either

public static Polynomial add(Polynomial p1, Polynomial p2)

{

/**** ADD CODE HERE ****/

return null;

}

//TODO: multiply this polynomial by a given term.

private void multiplyTerm(Term t)

{

/**** ADD CODE HERE ****/

}

//TODO: multiply two polynomials

public static Polynomial multiply(Polynomial p1, Polynomial p2)

{

/**** ADD CODE HERE ****/

return null;

}

//TODO: evaluate this polynomial.

// Hint: The time complexity of eval() must be order O(m),

// where m is the largest degree of the polynomial. Notice

// that the function SLinkedList.get(index) method is O(m),

// so if your eval() method were to call the get(index)

// method m times then your eval method would be O(m^2).

// Instead, use a Java enhanced for loop to iterate through

// the terms of an SLinkedList.

public BigInteger eval(BigInteger x)

{

/**** ADD CODE HERE ****/

return new BigInteger("0");

}

// Checks if this polynomial is same as the polynomial in the argument.

// Used for testing whether two polynomials have same content but occupy disjoint space in memory.

// Do not change this code, doing so may result in incorrect grades.

public boolean checkEqual(Polynomial p)

{

// Test for null pointer exceptions!!

// Clearly two polynomials are not same if they have different number of terms

if (polynomial == null || p.polynomial == null || size() != p.size())

return false;

int index = 0;

// Simultaneously traverse both this polynomial and argument.

for (Term term0 : polynomial)

{

// This is inefficient, ideally you'd use iterator for sequential access.

Term term1 = p.getTerm(index);

if (term0.getExponent() != term1.getExponent() || // Check if the exponents are not same

term0.getCoefficient().compareTo(term1.getCoefficient()) != 0 || // Check if the coefficients are not same

term1 == term0) // Check if the both term occupy same memory location.

return false;

index++;

}

return true;

}

// This method blindly adds a term to the end of LinkedList polynomial.

// Avoid using this method in your implementation as it is only used for testing.

// Do not change this code, doing so may result in incorrect grades.

public void addTermLast(Term t)

{

polynomial.addLast(t);

}

// This is used for testing multiplyTerm.

// Do not change this code, doing so may result in incorrect grades.

public void multiplyTermTest(Term t)

{

multiplyTerm(t);

}

@Override

public String toString()

{

if (polynomial.size() == 0) return "0";

return polynomial.toString();

}

}

STARTER CODE FOR SLinkedList

import java.lang.Iterable;

import java.util.Iterator;

/**

* A basic implementation of some methods in a singly linked list class.

* @author Michael Langer

* @modified by Sayantan Datta

*

* (Most of this code was adapted from textbooks

* e.g. by Frank Carrano, Mark Allen Weiss,

* Michael Goodrich and Roberto Tomassia)

*

* I put some Javadoc in this code, e.g. @param, @return

* But I do not expect you to do so in this course

* (and I generally don't do it when I am writing my own Java code)

*

*/

// The "extends" (rather than "implements") in the generic type definition is a Java detail that you don't need to think about.

public class SLinkedList> implements Iterable

{

// Fields

private SNode head;

private SNode tail;

private int size;

// Constructor

SLinkedList()

{

head = null;

tail = null;

size = 0;

}

/**

* Inserts the element to the specified position in this list

* where index is from 0 to size. If the position is size, then

* add element to the end of the list.

* @param i the position where the element should go

* @param element the element to be added

*/

public void add(int i, E element)

{

if ((i < 0) || (i > size))

throw new IndexOutOfBoundsException();

if (i == 0)

addFirst(element);

else if (i == size) // Bot necessary to do this test. Only do it because

addLast(element); // it is more efficient than what is below.

else

{

SNode previousNode = getNode(i-1); // undefined if i==0

SNode newNode = new SNode(element);

newNode.next = previousNode.next;

previousNode.next = newNode;

size++;

}

}

/*

* add a new element to front of list

* @param element the new element

*/

public void addFirst(E element)

{

SNode newNode = new SNode(element);

size++;

if (head == null)

{

head = newNode;

tail = head;

}

else

{

newNode.next = head; // Why not newNode.setNext(head) ? You could but you don't need to.

head = newNode; // i.e. Don't need to use get and set methods inside the class.

}

}

/*

* add a new element to the end of the list

* @param element the new element

*/

public void addLast(E element)

{

SNode newNode = new SNode(element);

size++;

if (head == null)

{

head = newNode;

tail = newNode;

}

else

{

tail.next = newNode;

tail = newNode;

}

}

/*

* remove all elements from the list

*/

public void clear()

{

head = null;

tail = null;

size = 0;

}

/*

* get the element at position i in the list (0,..., size -1 )

* @param i the index of the element

* @return the element to get

*/

public E get(int i)

{

return getNode(i).element;

}

public boolean isEmpty()

{

return (size == 0);

}

/*

* Removes the element at index i in 0 to size-1, and return it.

* @return the element at index i.

*/

public E remove(int i)

{

if ((i < 0) || (i >= size))

throw new IndexOutOfBoundsException();

else {

// first deal with special case that size == 1, i == 0

if ((size == 1) && (i == 0)) // only one node in list

{

size--;

SNode cur = head;

head = null;

tail = null;

return cur.element;

}

// Now we can assume that size > 1.

// We first deal with case that i == 0

SNode cur = head;

size--;

if (i == 0){

head = head.next;

return cur.element;

}

else // we can assume that i > 0;

{

cur = getNode(i-1);

SNode nodeToRemove = cur.next;

cur.next = nodeToRemove.next;

if (nodeToRemove.next == null) // removing the tail

tail = cur;

else

nodeToRemove.next = null; // be safe

return nodeToRemove.element;

}

}

}

/**

* Remove element at front of the list.

* @return first element in list

*/

public E removeFirst(){

return remove(0);

}

/**

* Remove element at back of list.

* @return last element

*/

public E removeLast(){

return remove(size-1);

}

/**

* Sets the ith element in the list.

* @param i the index of element to be set

* @param e the new element that replaces the old element

*/

public void set(int i, E e)

{

if ((i < 0) || (i >= size))

throw new IndexOutOfBoundsException();

else

getNode(i).element = e;

}

/**

* Show all elements in list. Alternatively I could have overriden the toString() method and then

* just print the object, since printing an object automatially calls the toString() method.

*/

public void show()

{

SNode cur = head;

while (cur != null)

{

System.out.print(" " + cur.element.toString());

cur = cur.next;

}

System.out.println(" (size is " + size + " )");

}

public int size()

{

return size;

}

/*

* TODO: Makes a deep copy of the this linked list.

* Hint: Use E.deepCopy().

*/

public SLinkedList deepClone()

{

/**** ADD CODE HERE ****/

return null;

}

@Override

public String toString()

{

String ret = "";

if (head == null)

return "";

// Hint: Use T.toString().

SNode current = head;

while (current != null)

{

ret = ret + current.element.toString();

current = current.next;

}

return ret;

}

@Override

public SLLIterator iterator()

{

SLLIterator iter = new SLLIterator(this);

return iter;

}

private class SLLIterator implements Iterator

{ // use a different generic type, since we're defining a new class here

SNode cur;

// constructor

SLLIterator(SLinkedList list)

{

cur = list.head;

}

@Override

public boolean hasNext()

{

return (cur != null);

}

@Override

public E next()

{

SNode tmp = cur;

cur = cur.next;

return tmp.element;

}

}

// The next two methods are private. The client has no access to the nodes of the linked list,

// but rather the client can only access the elements that are stored in the list.

/*

* @param index of node to get

* @return ith SNode of the linked list

*

*/

private SNode getNode(int i)

{

if ((i < 0) || (i >= size))

throw new IndexOutOfBoundsException();

else

{

if (i == 0) // only one node in list

return head;

else

{

int index = 0;

SNode cur = head;

while (index < i){

cur = cur.next;

index++;

}

return cur;

}

}

}

// inner class

private class SNode

{ // I have to use a different generic type since I am defining a class here.

private T element;

private SNode next;

SNode(T element){

this.element = element;

next = null;

}

}

}

CODE FOR THE TERM CLASS (YOU DONOT NEED TO MODIFY IT)

//package assignments2018.a2template;

import java.math.BigInteger;

/*

* This class Term represents a single term in the polynomial

*

* The terms with zero coefficients should be removed from the

* representation.

*

* Under no circumstances the exponent should be negative.

*/

public class Term implements DeepClone {

/* instance fields */

private int exponent;

private BigInteger coefficient;

/* Constructors */

public Term(int e, BigInteger c)

{

exponent = e;

coefficient = c;

}

// We must implement deepClone() method as the Term class implements the DeepClone interface.

// Returns a deep copy of the term. Hence the returned object resides in a different

// memory location than this object.

@Override

public Term deepClone()

{

return new Term(exponent, coefficient);

}

/* Instance methods */

BigInteger getCoefficient()

{

return coefficient;

}

int getExponent()

{

return exponent;

}

void setCoefficient(BigInteger d)

{

coefficient = d;

}

void setExponent(int a){

exponent = a;

}

// Hint: Notice that in your final submission, you are not supposed to use this

// method for evaluating a polynomial. This method is provided for

// validating your implementation of Horner's method.

BigInteger eval(BigInteger x){

BigInteger result = BigInteger.valueOf(1);

int n = exponent;

while (n != 0){

result = result.multiply(x);

n--;

}

return (result.multiply(coefficient));

}

@Override

public String toString()

{

String s = "";

// Check if the coefficient is less than zero.

if (coefficient.compareTo(new BigInteger("0")) < 0)

s += "-";

// Check if the coefficient is greater than zero.

else if (coefficient.compareTo(new BigInteger("0")) > 0)

s += "+";

// Check if the coefficient +1 or -1.

if (coefficient.abs().compareTo(new BigInteger("1")) != 0)

s += coefficient.abs();

// Check if the term is not a constant

if (exponent > 0)

{

s+="x";

if (exponent > 1){

s+="^" + exponent;

}

}

// If the term is a constant and coefficient is +1 or -1

else if (coefficient.abs().compareTo(new BigInteger("1")) == 0)

s+="1";

return s;

}

}

STARTER CODE FOR DEEPCLONE

//package assignments2018.a2template;

public interface DeepClone {

// Classes implementing this interface must implement deepClone() method.

public T deepClone();

}

CODE FOR TESTER: TO CHECK IF YOUR CODE IS OKAY YOU HAVE TO MAKE SOME CHANGES TO SEE THAT

import java.math.BigInteger;

public class PolynomialTester {

private static void testClone()

{

Polynomial poly = new Polynomial();

poly.addTermLast(new Term(0, new BigInteger("1")));

poly.addTermLast(new Term(1, new BigInteger("2")));

poly.addTermLast(new Term(2, new BigInteger("3")));

poly.addTermLast(new Term(3, new BigInteger("4")));

poly.addTermLast(new Term(4, new BigInteger("5")));

Polynomial clone = poly.deepClone();

if (clone.checkEqual(poly))

{

System.out.println("Passed: deepClone()");

return;

}

System.out.println("Failed: deepClone()");

}

// Tests if the terms are arranged in correct order.

private static void testAddTerm_1()

{

Polynomial p1 = new Polynomial(); // reference polynomial

Polynomial p2 = new Polynomial();

p1.addTermLast(new Term(4, new BigInteger("4")));

p1.addTermLast(new Term(3, new BigInteger("3")));

p1.addTermLast(new Term(2, new BigInteger("2")));

p1.addTermLast(new Term(1, new BigInteger("1")));

p2.addTerm(new Term(1, new BigInteger("1")));

p2.addTerm(new Term(2, new BigInteger("2")));

p2.addTerm(new Term(3, new BigInteger("3")));

p2.addTerm(new Term(4, new BigInteger("4")));

if (p1.size() != 0 && p2.size() != 0 && p1.checkEqual(p2))

{

System.out.println("Passed: addTerm() - Test1");

return;

}

System.out.println("Failed: addTerm() - Test1");

}

// Check if adding a new term updates/removes an existing term in the polynomial.

private static void testAddTerm_2()

{

Polynomial p1 = new Polynomial();

Polynomial p2 = new Polynomial(); // reference polynomial

p1.addTerm(new Term(4, new BigInteger("4")));

p1.addTerm(new Term(3, new BigInteger("3")));

p1.addTerm(new Term(2, new BigInteger("2")));

p1.addTerm(new Term(1, new BigInteger("1")));

p1.addTerm(new Term(2, new BigInteger("-1")));

p2.addTermLast(new Term(4, new BigInteger("4")));

p2.addTermLast(new Term(3, new BigInteger("3")));

p2.addTermLast(new Term(2, new BigInteger("1")));

p2.addTermLast(new Term(1, new BigInteger("1")));

if (p1.size() != 0 && p2.size() != 0 && p1.checkEqual(p2))

{

System.out.println("Passed: addTerm() - Test2");

return;

}

System.out.println("Failed: addTerm() - Test2");

}

// Test case when there are no terms with same exponent in two polynomial

private static void testAdd_1()

{

Polynomial p1 = new Polynomial();

Polynomial p2 = new Polynomial();

p1.addTerm(new Term(2, new BigInteger("2")));

p1.addTerm(new Term(0, new BigInteger("1")));

p2.addTerm(new Term(3, new BigInteger("1")));

p2.addTerm(new Term(4, new BigInteger("2")));

Polynomial sum = Polynomial.add(p1, p2);

Polynomial expectedSum = new Polynomial(); // reference

expectedSum.addTermLast(new Term(4, new BigInteger("2")));

expectedSum.addTermLast(new Term(3, new BigInteger("1")));

expectedSum.addTermLast(new Term(2, new BigInteger("2")));

expectedSum.addTermLast(new Term(0, new BigInteger("1")));

if (sum != null && expectedSum.checkEqual(sum))

{

System.out.println("Passed: add() - Test 1");

return;

}

System.out.println("Failed: add() - Test 1");

}

// Test case when there are terms with same exponent in two polynomial

private static void testAdd_2()

{

Polynomial p1 = new Polynomial();

Polynomial p2 = new Polynomial();

p1.addTerm(new Term(2, new BigInteger("2")));

p1.addTerm(new Term(0, new BigInteger("1")));

p1.addTerm(new Term(3, new BigInteger("1")));

p1.addTerm(new Term(4, new BigInteger("2")));

p2.addTerm(new Term(3, new BigInteger("2")));

p2.addTerm(new Term(2, new BigInteger("5")));

Polynomial sum = Polynomial.add(p1, p2);

Polynomial expectedSum = new Polynomial(); //reference

expectedSum.addTermLast(new Term(4, new BigInteger("2")));

expectedSum.addTermLast(new Term(3, new BigInteger("3")));

expectedSum.addTermLast(new Term(2, new BigInteger("7")));

expectedSum.addTermLast(new Term(0, new BigInteger("1")));

if (sum != null && expectedSum.checkEqual(sum))

{

System.out.println("Passed: add() - Test 2");

return;

}

System.out.println("Failed: add() - Test 2");

}

// Small polynomial test

private static void testEval_1()

{

Polynomial p1 = new Polynomial();

p1.addTermLast(new Term(4, new BigInteger("2")));

p1.addTermLast(new Term(3, new BigInteger("1")));

p1.addTermLast(new Term(2, new BigInteger("2")));

p1.addTermLast(new Term(0, new BigInteger("1")));

if (p1.eval(new BigInteger("2")).compareTo(new BigInteger("49")) == 0)

{

System.out.println("Passed: eval() - Test 1");

return;

}

System.out.println("Failed: eval()- Test 1");

}

// Long polynomial test. Creates a polynomial with a large number of terms and each term has

// coefficient 1 and we are evaluating at x=1, so c_i x^i = 1 for each of these terms.

// Thus the polynomial would have value equal to the number of terms, i.e. 1 + 1 + .... + 1 = number of terms

private static void testEval_2()

{

Polynomial p1 = new Polynomial();

for (int i = 0; i < 1000000; i++)

p1.addTermLast(new Term(1000000 - i - 1, new BigInteger("1")));

if (p1.eval(new BigInteger("1")).compareTo(new BigInteger("1000000")) == 0)

{

System.out.println("Passed: eval() - Test 2");

return;

}

System.out.println("Failed: eval()- Test 2");

}

private static void testMultiplyTerm()

{

Polynomial p1 = new Polynomial();

p1.addTermLast(new Term(2, new BigInteger("2")));

p1.addTermLast(new Term(0, new BigInteger("1")));

p1.multiplyTermTest(new Term(1, new BigInteger("3")));

Polynomial result = new Polynomial();

result.addTermLast(new Term(3, new BigInteger("6")));

result.addTermLast(new Term(1, new BigInteger("3")));

if (p1.size() != 0 && p1.checkEqual(result))

{

System.out.println("Passed: multiplyTerm()");

return;

}

System.out.println("Failed: multiplyTerm()");

}

private static void testMultiply()

{

Polynomial p1 = new Polynomial();

Polynomial p2 = new Polynomial();

p1.addTermLast(new Term(2, new BigInteger("2")));

p1.addTermLast(new Term(0, new BigInteger("1")));

p2.addTermLast(new Term(2, new BigInteger("2")));

p2.addTermLast(new Term(0, new BigInteger("1")));

Polynomial product = Polynomial.multiply(p1, p2);

Polynomial expectedProduct = new Polynomial();

expectedProduct.addTermLast(new Term(4, new BigInteger("4")));

expectedProduct.addTermLast(new Term(2, new BigInteger("4")));

expectedProduct.addTermLast(new Term(0, new BigInteger("1")));

if (product != null && product.checkEqual(expectedProduct))

{

System.out.println("Passed: multiply()");

return;

}

System.out.println("Failed: multiply()");

}

public static void main(String[] args)

{

testClone();

testAddTerm_1();

testAddTerm_2();

testAdd_1();

testAdd_2();

testEval_1();

testEval_2();

testMultiplyTerm();

testMultiply();

}

}