Contents:

Advice

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)

As you are completing this assignment, type out your answers to parts 0-3 in hw-poly/src/main/java/poly/answers.txt, and make sure to commit and push your changes to this file along with the rest of the assignment.

You will become familiar with the test suite for this homework while testing and debugging your work. In future homeworks, it will be your job to implement a test suite to evaluate your code, so it is also reccomended that you take notice of the structure and syntax of our test suite. We use a specific testing framework, JUnit 4 (more on that later), which has specific syntax for testing different outcomes. It is worth taking some time to look at the general expectations of a test suite and remember where to look for an example of syntax specifics.

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.

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 -42x100 + 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 + ... + p i-1 where pi is the ith 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.

Answer the following questions. For each loop that you write in your pseudocode, you should write the loop invariant next to it. You do not need to push the assertions through the entire loop or write the full proof of correctness for the algorithm, but you should have at least the invariant written down, and have an idea in your head of why it is correct.

  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.)

Since your answer will be ASCII text, you won't be able to use italics and subscripts in your answer. You can dispense with italics, and you can represent “tp” as t_p and “x2” as x^2.

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 in your answers.txt file. For full credit, your answers should be short and to the point, 1-3 sentences max, unless otherwise specified. 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. Include both methods that need to change in order to still adhere to the spec correctly, and also methods that could be different if they were implemented with this new rep invariant. For each changed piece of code, describe the changes informally in 1-2 sentences max, 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.

Answer the following question in answers.txt. Again keep your answers short and to the point. 1-3 sentences max, unless otherwise specified.

  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 RatTerms 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, in 1-4 sentences max, describe the changes 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, in 1-4 sentences max, describe the changes 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).

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: Right click on a method name » Find Usages)

For this assignment you should not use Java's Streams API instead of regular loops. We want to gain additional practice in this assignment with specification and development of correct loops using invariants and the techniques we've learned. Streams can be very useful, but they provide a very different model for processing collections and reasoning about correctness, which we have not explored. You will be free to use streams in later projects if you know about or want to learn about them, but you should use traditional loops for now.

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

Answer the following questions in answers.txt. Again keep your answers short and to the point. 1-3 sentences max, unless otherwise specified.

  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 and 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 to answer 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.

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

Hints

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

long division example

In this example, the result of truncating division is 1⁄ 3 x2 - 2⁄9 because truncating division discards the remainder.