Description:

In this optional project, we will try to find an optimal algorithm to evaluate a given

monomial x$^$n with the minimum number of multiplications. We will practice the Bottom

Up Dynamic Programming approach to avoid any redundant computation. This new

algorithm will incorporate both the Repeated Squaring and the Repeated Cubing algorithms so that the new algorithm performs better than the Repeated Squaring and the

Repeated Cubing algorithms.

Requirements:

$1.($Build the dictionary$)$

The Dynamic Programming relies on an underlying data structure $($here an array$)$

to store the intermediate computation results, which is called a dictionary. Here we

will use the bottom up approach to build this dictionary. Our recursive algorithms

will retrieve the data from the dictionary and add the new data into the dictionary.

$2.($Modify Repeated Squaring and Repeated Cubing Methods$)$

Since all the history data comes from the dictionary, we need to modify the original

Repeated Squaring method to connect to the dictionary. Similarly, we also modify

the original Repeated Cubing method.

$3.($Mix Repeated Squaring and Repeated Cubing Methods$)$

Our new algorithm should be built on top of both the Repeated Squaring and the

Repeated Cubing methods. Since the data comes from the dictionary, the recursion

stack should not be very deep.

$4.($Output$)$

To show the performance of this algorithm, we use the number of multiplications

instead of the response times to measure its efficiency. You print out the number

of multiplications for calculating x$^$n with n between $100$ and $200($inclusive$)$ by

this new algorithm. At the same time, you also need to print out the number of

multiplications for both the Pure Repeated Squaring and the Pure Repeated Cubing

methods for side$-$by$-$side comparisons.

$5.($Extra Credit Allocations$)$

If you only print out the multiplication numbers without showing how to do the

multiplications, you get $2\%$ extra credit; if you can also produce the multiplication

ways on the screen for each x$^$n

$,$ then you get another $1\%$ extra credit.