Description: We will compare three different algorithms that are used to evaluate polynomials. The goal is to understand the importance of the efficiency of an algorithm. The first two algorithms are based on the straightforward method, but they use different ways to evaluate the monomials (that is, x^k). The third algorithm uses the Horners Rule to evaluate polynomials. We will use random number generating functions to create large polynomials to be evaluated by these three algorithms, and compare their response times.

Requirements: 1. FORMAT YOUR PROGRAM It is desirable to use Java as the programming language. But if you use C/C++ or Python, it is still acceptable. When you submit your project, place your program or programs in one folder with your name and Proj1, P1, Project1, etc. as the folder name, then zip your folder and submit it.

If you use Java, try to put your program in the package: edu.school.algorithms. In this way, it is more convenient to run your programs. For those who use an online compiler, you can skip this step.

2. GENERATE THE POLYNOMIAL COEFFICIENTS AND THE POINT TO BE EVALUATED AT Each coefficient of the polynomial should be an integer between 1 and 100 inclusive. You use an integer array to store all the coefficients generated, and the size of the array is determined by the degree of the polynomial. The degree of the polynomial is hard-coded in your program. Based on my experiments, a good choice of the degree number should be around 200, 000 so as to see some relatively big difference.

The value of the variable x should be a double between 0.0 and 1.0, exclusive. The reason to choose the value in this range is simple: We can easily avoid the overflow problem. If the value is 0.0 or 1.0, the evaluation time is very fast, and it does not reflect the general case. So try to avoid 0.0 and 1.0 to be the value of x. You need to design a way to generate a number in the open interval (0, 1) directly. For example, you can generate a double number in the interval [0.01, 0.99], which avoids 0.0 and 1.0 easily.

3. USER'S INTERFACE In order to provide the users a convenient way to test your program, you should create a simple users interface. When a user runs your program, you display a simple menu by printing out appropriate messages on the screen. Your program asks the user to choose one of the three methods (described below) to evaluate the polynomial using 1, 2, or 3 to represent the selected method. Put your testing part in a while loop, so that the user can test all the methods in one execution, and use 0 for the exit code.

4. MONOMIAL EVALUATION AND REPEATED SQUARING TECHNIQUE In the first two methods, we use the straightforward method to evaluate the poly-nomials, in which we need to evaluate the monomials x^k. Our first algorithm just uses direct multiplications in a for-loop. Our second algorithm uses the repeated squaring technique to calculate the monomials.

5. HORNER'S RULE Our third algorithm uses the Horners Rule to evaluate the whole polynomial with-out calculating the monomials. The main objective of this project is to see how much faster this algorithm is comparing with the first two simple algorithms.

6. OUTPUT Before you display the menu on the screen, you print out the degree number of the polynomial first, because this number only needs to be displayed once. Then for each algorithm, you need to display the result first, and then the execution time in milliseconds. We expect that all three algorithms produce the same evaluation result. After the user enters 0 code to terminate the program, display a (Bye!) message to tell the user that the whole program completes the execution.