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.
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:
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 x^{2} - 2x + 1. Another example is -42
x^{100} + 22x^{12} + 5x^{10}. 22x^{12}
is called a “term”;
its degree is 12 and its coefficient is 22. Here is pseudocode for polynomial addition:
set
r = q by making a term-by-term copy of all terms in
q to rforeach
term, t_{p}, in
p:
if
any term, t_{r}, in r has the same degree as
t_{p},
then
replace t_{r} in r with the sum of
t_{p} and t_{r}else
insert t_{p} 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 t_{p} and t_{r}. 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:
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.
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 (2x^{2} + 5) + (3x^{2} - 4x):
foreach
term, t_{p}, in p
if
any term, t_{r}, in r has the same
degree as t_{p}] YES, t_{r} = 3x^{2}
then
replace t_{r} in r with the sum of
t_{p} and t_{r}] t_{p} + t_{r}
= 5x^{2}, so now r = (5x^{2} - 4x)
else
insert t_{p} into r as a new term]
if
any term, t_{r}, in r has the same
degree as t_{p}] NO
then
replace t_{r} in r with the sum of
t_{p} and t_{r}]
else
insert t_{p} into r as a new term]
r = (5x^{2} - 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 “t_{p}” as t_p
and
“x^{2}” 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 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.
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.
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.)
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?)
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 questions, writing your answers in the same file as Parts 0 and 1. Again keep your answers to 2-3 sentences.
checkRep
(at the beginning of methods, the end of methods, the
beginning of constructors, the end of constructors, some combination)? Why?
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
).
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).
Which set of additional RatTerm
invariants (coeff.isNaN() ⇒ expt = 0;
coeff.equals(RatNum.ZERO) ⇒ expt = 0; both; neither) do you prefer? Why?
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
.
Answer the following questions, writing your answers in the same file as previous parts. Again keep your answers to 2-3 sentences, maximum.
checkRep
(at the beginning of methods, the end of methods, the
beginning of constructors, the end of constructors, some combination)? Why?
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. :)
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.
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
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.
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.
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.
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 ^{1}⁄_{3} x^{2} - ^{2}⁄_{9} because truncating division discards the remainder.