Contents:

We recommend that you read through the homework before you begin work to get a sense of the homework overall. It is long but broken into reasonably sized chunks.

Beware, this is your first real programming assignment for this class. In previous quarters, students have often found themselves surprised by how much work this assignment involves, and end up using a late day and/or not finishing. So please start early.

Check out the Hints section at the bottom of this page first, the advice down there will likely come in handy as you work through the entire assignment.

## Introduction

This homework focuses on reading and interpreting specifications, and reading and writing Java code. It also introduces `checkRep` methods and testing strategies. You will complete the implementation of a graphing polynomial calculator, and you will answer questions about both the code you are given and the code you are going to write.

To complete this homework, you will need to know:

1. Some algebra (rational and polynomial arithmetic)
2. Java programming (methods, classes, fields, variables, objects, loops, arithmetic, etc.)
3. How to read procedural specifications (requires, modifies, effects)

## Part 0: Polynomial Arithmetic Algorithm

When we release each homework assignment, we push the new starter files to your repository in GitLab, so you should obtain these new files by pulling from git.

As you are completing this assignment, create a PDF file with your written answers to Parts 0-3. Submit this file to Gradescope when you turn in the assignment.

For this part you will write pseudocode algorithms for arithmetic operations applied to single-variable polynomial equations. An example polynomial is x2 - 2x + 1. Another example is -42 x100 + 22x12 + 5x10. `22x12` is called a “term”; its degree is 12 and its coefficient is 22. Here is pseudocode for polynomial addition:

• r = p + q:
• `set` r = q by making a term-by-term copy of all terms in q to r
• {Inv: r = q + p0 + p1 + ... + pi-1, where pj is the jth term in p}
• `foreach` term, tp, `in` p:
• `if` any term, tr, in r has the same degree as tp,
• `then` replace tr in r with the sum of tp and tr
• `else` insert tp into r as a new term

You may use ordinary arithmetic operations on individual terms of polynomial equations without defining them yourself (but only operations on two terms, not on one term and one polynomial, or some other “mixture” of types). For the above example, the algorithm uses addition on the terms tp and tr. Furthermore, after defining an algorithm, you may use it to define other algorithms. For example, if helpful, you may use polynomial addition in your algorithms for multiplication and division. Be sure your types are correct: if addition is defined over terms, and is defined over polynomials, that does not mean you can add a term to a polynomial unless you have also defined that case.

1. Write a pseudocode algorithm for multiplication.
2. Write a pseudocode algorithm for truncating division, that satisfies the specification of `RatPoly.div`. Also, see the Hints section for a diagram illustrating polynomial division. For this question, you do not need to handle division by zero; however, you will need to do so for the Java programming exercise later in this assignment.
3. Illustrate your division algorithm running on this example: (x3+x-1) / (x+1) = x2-x+2

Be sure to show the values of all variables in your pseudocode at the beginning of each loop iteration.

Here is an example illustration of the addition algorithm running on (2x2 + 5) + (3x2 - 4x):

• p = (2x2 + 5)
• q = (3x2 - 4x)
• r = copy of q = (3x2 - 4x)
• `foreach` term, tp, in p
• Iteration 1: tp = 2x2, r = (3x2 - 4x), p = (2x2 + 5), q = (3x2 - 4x)
• [`if` any term, tr, in r has the same degree as tp] YES, tr = 3x2
• [`then` replace tr in r with the sum of tp and tr] tp + tr = 5x2, so now r = (5x2 - 4x)
• [`else` insert tp into r as a new term]
• Iteration 2: tp = 5, r = (5x2 - 4x), p = (2x2 + 5), q = (3x2 - 4x)
• [`if` any term, tr, in r has the same degree as tp] NO
• [`then` replace tr in r with the sum of tp and tr]
• [`else` insert tp into r as a new term] r = (5x2 - 4x + 5)
• We are done! r = (5x2 - 4x + 5)

(Notice that the values of p and q did not change throughout the execution of the algorithm. Thus, this algorithm works when p and q are required to be immutable (unchanged), which can be a desirable trait for a piece of code. You will learn about immutable objects as you progress on this homework.)

If you choose, you can simply write your answers as text in the PDF. In this case, you can dispense with italics, and you can represent “tp” as `t_p` and “x2” as `x^2`. You may also typeset your responses to use fancier formatting - this is your choice, and has no impact on grading. Whatever you do, just make sure your solution is easy to read.

## Part 1: RatNum

Part 1 does not involve writing code, but you do have to answer written questions. Read the specifications for `RatNum`, a class representing rational numbers. Then read the provided implementation, `RatNum.java`.

You will likely want to look at the code in `RatNumTest.java` to see example usages of the RatNum class (albeit in the context of a test driver, rather than application code).

Answer the following questions, writing your answers in the same file as in Part 0. Two or three sentences should be enough to answer each question. For full credit, your answers should be short and to the point. Answers that are excessively long or contain irrelevant information will not receive full credit.

1. Suppose the representation invariant were weakened so that it did not require that the `numer` and `denom` fields be stored in reduced form. This means that the method implementations could no longer assume this invariant held on entry to the method, but they also would no longer be required to enforce the invariant on exit. The new rep invariant would then be:
`// Rep Invariant for every RatNum r: ( r.denom >= 0 )`

List the method or constructor implementations that might have been different if the class had been designed with this new rep invariant instead. For each changed piece of code, describe the changes briefly and informally, and compare the advantages and disadvantages (in terms of code clarity and/or execution efficiency) of each change. Note that the new implementations must still adhere to the given spec; in particular, `RatNum.toString()` needs to output fractions in reduced form.

2. `add`, `sub`, `mul`, and `div` all end with a statement of the form `return new RatNum ( numerExpr , denomExpr);`. Imagine an implementation of the same function except the last statement is:
```this.numer = numerExpr;
this.denom = denomExpr;
return this;
```

For this question, pretend that the `this.numer` and `this.denom` fields are not declared as `final` so that these assignments compile properly. How would the above changes fail to meet the specifications of the methods and fail to meet the specifications of the `RatNum` class? (Hint: Look at the `@spec.requires` and `@spec.effects` clauses, or lack thereof.)

3. Calls to `checkRep` are supposed to catch violations of the rep invariant. In general, it is recommended that you call `checkRep` at the beginning and end of every method. In the case of `RatNum`, why is it sufficient to call `checkRep` only at the end of the constructors? (Hint: Could a method ever modify a `RatNum` such that it violates its representation invariant? Could a method change a `RatNum` at all? How are changes to instances of `RatNum` prevented?)

## Part 2: RatTerm

Read the specifications for the `RatTerm` class, making sure you understand the overview for `RatTerm` and the specifications for the given methods.

Read the provided skeletal implementation of `RatTerm.java`, especially the comments describing how you are to use the provided fields to implement this class.

Fill in an implementation for the methods in the skeleton of `RatTerm`. You may define new private helper methods as you like. You may not add public methods; the external interface must remain the same. We have provided full implementations of some methods; you do not need to change them, and we recommend that you do not do so.

Throughout this assignment, if you define new methods, you must specify them completely. You can consider the specifications of existing methods (where you fill in the body) to be adequate. You should document any code you write, but please do not over-document.

We have provided a `checkRep()` method in `RatTerm` that tests whether or not a `RatTerm` instance violates the representation invariant. We recommend you use `checkRep()` where appropriate in the code you write. Think about the issues discussed in the last question of Part 1 when deciding where to call `checkRep`.

We have provided a fairly rigorous test suite in `RatTermTest.java`. You can run the test suite to evaluate your progress and the correctness of your code. To run the test suite, you should refer to the editing, compiling, running, and testing Java programs handout.

1. Where did you include calls to `checkRep` (at the beginning of methods, the end of methods, the beginning of constructors, the end of constructors, some combination)? Why?
2. Suppose we weakened the representation invariant so that we did not require `RatTerm`s with zero coefficients to have zero exponents. This means that the method implementations could no longer assume this invariant held on entry to the method, but they also no longer were required to enforce the invariant on exit. List which method or constructor implementations might be different if the class was implemented with this new rep invariant instead. For each changed piece of code, describe the changes briefly and informally, and compare the advantages and disadvantages (in terms of code clarity and/or execution efficiency) of each change. Note that the new implementations must still adhere to the given spec; in particular, `RatTerm.toString()` still cannot produce a term with a zero coefficient (except `0`).
3. In the case of the zero `RatTerm`, all instances must have the same exponent (`0`). No such restriction was placed on `NaN` `RatTerm`'s. Imagine that such a restriction was enforced by changing the representation invariant to include the requirement:
```coeff.isNaN() ==> expt = 0.
```

This means that the method implementations could assume this invariant held on entry to the method, but they would also be required to enforce the invariant on exit. List which method or constructor implementations might be different if the class was implemented with this new rep invariant instead. For each changed piece of code, describe the changes briefly and informally, and compare the advantages and disadvantages (in terms of code clarity and/or execution efficiency) of each change. Note that the new implementations must still adhere to the given spec (except for the part where terms like `NaN*x^74` are explicitly allowed).

4. Which set of additional `RatTerm` invariants (coeff.isNaN() ⇒ expt = 0; coeff.equals(RatNum.ZERO) ⇒ expt = 0; both; neither) do you prefer? Why?

## Part 3: RatPoly

Following the same procedure given in Part 2, read over the specifications for the `RatPoly` class and its methods and fill in the blanks for `RatPoly.java`. The same rules apply here (you may add private helper methods as you like, make sure to specify them fully if you do). Since this part depends on Part 2, you should not begin it until you have completed Part 2 and the `RatTermTest` test suite runs without any errors.

You should figure out and write all loop invariants for any non-trivial loops you write in `RatPoly.java` before writing the code. By “non-trivial,” we mean any loop that's more complicated than, for example, setting all elements in an array to zero. If you're unsure if your loop qualifies as “trivial,” it's probably best to include the invariant. You can write the invariant as a comment on the line immediately before your loop. Because we haven't discussed the details of writing invariants for `for` loops, you can be looser with your notation. Remember that comments are meant to be read by humans, so as long as your comment clearly and unambiguously communicates the loop invariant, you don't need to worry too much about exact formatting. (Remember that a picture alone is not sufficient as an invariant, however.) You do not need to push assertions through the loop body or prove that your loop maintains the invariant in the comments, though you should have at least a basic understanding of why your loop does. After all, if you can't justify why your loop maintains an invariant, you might have just introduced a bug in your code! We recommend you write your loop with an invariant already in mind, as opposed to trying to write an invariant after you've created the loop. This will make it easier to write a clean, understandable invariant, as well as clean, understandable, and bug-free code.

You may also want to look at the specifications for the java.util.List interface, especially the `get()`, `add()`, `set()`, and `size()` methods.

You are welcome to do what you like with the two provided private helper methods in `RatPoly`, ``` scaleCoeff``` and `incremExpt`. You may implement them exactly as given, implement variants with different specifications, or even delete them; and you may add your own private helper methods. However, you must make sure that every private helper method in the final version of the class has an accurate specification and is not still an unimplemented skeleton (i.e. delete the provided methods if you don't use them). Note that you're also free to change `sortedInsert` if you really want to, but it's highly recommended that you implement it exactly as specified. Take extra care with `sortedInsert`, as some of the staff provided code in `RatPoly` relies on it working as specified. If you choose to modify or remove it, you must investigate whether you've broken the staff code by doing so, and fix it if necessary. (You can use IntelliJ's "Find Usages" feature to help you with this.)

Make sure your code passes all the tests in `RatPolyTest.java`.

1. Where did you include calls to `checkRep` (at the beginning of methods, the end of methods, the beginning of constructors, the end of constructors, some combination)? Why?
2. In RatPoly, we represented polynomials by using a list of RatTerms. Imagine that instead, we just kept track of the RatNum coefficients and int exponents of each term as two separate lists, where the ith term in the polynomial has coefficient coefflist.get(i) and degree exptlist.get(i). What are the advantages of disadvantages of representing a RatPoly like this? Which representation do you think is better, and why?

## Part 4: RatPolyStack

Following the same procedure given in Part 3, read over the specifications for the `RatPolyStack` class and its methods and fill in the blanks for `RatPolyStack.java`. The same rules apply here (you may add private helper methods as you like). Since this part depends on Parts 2 and 3, you should not begin it until you have completed Parts 2 and 3 and the `RatTermTest` and `RatPolyTest` test suites run without any errors.

Make sure your code passes all the tests in `RatPolyStackTest.java`.

No questions this time, but make sure to think about the same ideas discussed previously to aid in making your design choices. :)

## Part 5: CalculatorFrame

Now that RatPoly and RatPolyStack are finished, you can run the calculator application. You can do this by running the `runCalculator` gradle task (found under hw-poly > tasks > homework in the IntelliJ gradle menu). This allows you to input polynomials and perform arithmetic operations on them, through a point-and-click user interface. The calculator graphs the resulting polynomials as well. It works by making use of all the code you just implemented - we're just providing the pretty interface.

When you run the calculator, a window will pop up with a stack on the left, a graph display on the right, a text area to input polynomials into, and a set of buttons along the bottom. Click the buttons to input polynomials and to perform manipulations of the polynomials on the stack. When you input the polynomials, be sure to input them in the same format used by RatPoly.toString(). The graph display will update on the fly, graphing the top four elements of the stack.

## How to Turn In Your Homework

At the end of each assignment, you must refer to the Assignment Submission Handout and closely follow the steps listed to submit your assignment. Do not forget to double check your submission as described in that handout - you are responsible for any issues if your code does not run when we try to grade it.

Use the tag name hw4-final for this assignment. To verify your assignment on attu, you can use the gradle task: `hw-poly:validate` to check for common errors such as your code not compiling or not passing tests. However, validation is not guaranteed to catch all errors in your code.

Your TA should be able to find the following in the `hw-poly/src/main/java/poly` directory of your repository:

• `RatTerm.java`
• `RatPoly.java`
• `RatPolyStack.java`

## Hints

• The `javadoc` Gradle task might come in handy when reading the specifications for all the methods in a nicely-formatted way. In the Gradle window, under the "poly" project's tasks, run the `javadoc` task in the "documentation" group. This will generate a formatted javadoc page (just like the ones in the Java standard library) based on the javadoc comments in the provided code (plus any additional ones that you write). To view this documentation, open `hw-poly/build/docs/javadoc/index.html` in your favorite browser. You can right-click index.html in IntelliJ and choose "Open in Browser" to do this.
• For writing pseudocode: it's generally acceptable to describe O(1) operations in English in one line of pseudocode. Any operation that isn't O(1) (like a loop over some number of things) should probably be written out/explained in more than just one line.
• All the unfinished methods in `RatTerm`, `RatPoly` and `RatPolyStack` throw RuntimeExceptions. When you implement a method, be sure to remove the `throw new RuntimeException();` statement. To help you find them, we have also added a `TODO:` comment in each of these methods.
• IntelliJ has a "TODO" window (View > Tool Windows > TODO) that could come in handy to find all the TODO comments that we left for you, marking methods you need to implement.
• Think before you code! The polynomial arithmetic functions are not difficult, but if you begin implementation without a specific plan, it is easy to get yourself into a terrible mess.
• The most important method in your `RatPoly` class will probably be `sortedInsert`. Take special care with this method, and make sure you implement the entire spec exactly as written. Note that some of the provided code uses `sortedInsert` and relies on the specification that we provide.
• The provided test suites in this homework are the same ones we will use to grade your implementation. You can consider the provided set of tests to be rigorous enough that you do not need to write your own tests. (In future homework assignments you will need to write tests.) If you would like to write your own tests to aid in debugging, however, you're welcome to do so. Make sure your code passes all tests before turning in your assignment.

Division of rational polynomials is similar to long division as taught in grade school. We draw an example here:

In this example, the result of truncating division is 13 x2 - 29 because truncating division discards the remainder.