You are given an array of integers A, which represent the coefficients of an equation with a single variable x. These coefficients are ordered from low to high. That is, A[0] is the constant term, A[1] is for x, A[2] is for x

2 and so on. For example, suppose A = [6, 5, 1], the equation is

for 6 5x + x 2 . You are to implement a function which finds the smallest non-negative root of the

equation within certain range: int ECFindRoot(int *listCoeffs, int degree, int xmax) ;

1

where listCoeffs is the pointer to the array of coefficients, degree is the highest degree of the equation, and xmax is the maximum value of the root. This function return the found smallest root (whose value is at most xmax) or -1 if there is no root. The following are what you need to do. 1. You should first ensure your code passes the provided test cases. These test cases are included in the autograder tests. If your code passes these test cases, you earn some points. 2. Then yous should ensure your code runs efficiently when the degree of the equation increases. You should analyze your code: what is the running time of it? Suppose d is the equation maximum degree. What is the running time for checking for a specific value of x whether x is the root? If your code for this step runs in O(d 2 ), that will be too slow. You should make

your code run in O(d) time for this step. We will have run-time check for this.

5 extra credits When dealing with numerical problems like this exercise, numerical overflow can be an issue. Numerical overflow can occur if the numerical value you computed becomes too large and is beyond the range of the data type. In this exercise you are asked to find the root of data type int. You may think you can somehow fix the problem by using data type long. This is not what I want. To get the extra credit, you must still use data type int; you need to change your implementation if overflow occurs.\

*** STARTER CODE ***

// This function returns the smallest non-negative integral root of a polynomial (as specified by a list of coefficients and degree) that is no larger than xmax. Return -1 if there is no roots within the range.

//To be specific: for each integer 0 <=i <= degree, listCoeffs[d] = the coefficient of the degree d term. For example,

int ECFindRoot(int *listCoeffs, int degree, int xmax)

{

// listCoeffs: pointer to the array of integers as the coefficients of a polynomial; listCoeffs[0] is the constant term and so on

// degree: highest degree term. That is, the number of coefficients in the array = degree+1

// xmax: the largest value of root to search

// your code here

}

**** TESTER CODE ****

// Test code for ECFindRoot

// To build: c++ ECFindRootTest.cpp -o test

// To test: ./test

#include

using namespace std;

#include "ECFindRoot.cpp"

int main()

{

int test1[] = {4, -4, 1};

// root = 2 for 4-4x+x^2=0

cout << ECFindRoot(test1, 2, 10) << endl;

// should return -1 (no root)

int test2[] = {1, -3, 1};

cout << ECFindRoot(test2, 2, 10) << endl;

// should return -1

cout << ECFindRoot(test2, 0, 10) << endl;

}