Problem $3$: Polynomial division $(10$ pts$.$: Pseudocode, invariants and proofs: $5$ pts$.,$ Java code: $5$ pts$.$ autograded$)$

Use the definition of polynomial division provided below:

Given two polynomials u and v $,$ with $v0,$ we can divide u by v to obtain a quotient polynomial q and a remainder polynomial $r$ satisfying the condition $u=q**v+r,$ where the degree of $r$ is strictly less than the degree of v $,$ the degree of q is no greater than the degree of u $,$ and r and q have no negative exponents.

For the purposes of this class, the operation $\frac{u}{v}$ returns q as defined above.

The following are examples of division's behavior:

$\frac{x^3-2**x+3}{3**x^2}=\frac{1}{3}**x($with $r=-2**x+3).$

$\frac{x^2+2**x+15}{2**x^3}=0($with $r=x^2+2**x+15).$

$\frac{x^3+x-1}{x+1}=x^2-x+2($with $r=-3).$

Note that this truncating behavior is similar to the behavior of integer division on computers.

Do the following:

$(1)$ Write a pseudocode algorithm for polynomial division. Write your answer in the file answers$/$problem$3.$pdf$.$

$(2)$ When writing pseudocode use symbols,,$+-,$ and $/$ to express rational number and polynomial arithmetic. You may also use $u[i]$ to retrieve the coefficient at power $i$ of polynomial u $,$ as well as $c**x^i$ to denote the single$-$term polynomial of degree i and coefficient c $.$

$(3)$ State the loop invariant for the main loop and prove partial correctness. Write your answer in the file answers$/$problem$3.$pdf$.$ For the proof question, you do not need to handle division by zero; however, you will need to do so in the Java program.

Important: write your pseudocode, invariants, and proofs first, then write the Java code. Going backwards will be harder.

$(4)$ Complete the public method public RatPoly div$($RatPoly$)$ in the RatPoly class and transfer your pseudocode algorithm into div. You may assume that the divisor p is non$-$null. If p is zero div returns some q such that q$.$isNaN is true. As with the other operations $($e$.$g$.,$ mul$),$ if this.isNaN or p$.$isNaN, div returns some q such that q$.$isNaN is true.

There is an extensive test suite for division in RatPolyDivideTest.java. You can run this test suite to evaluate your progress and the correctness of your code.