Quick link:
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 reasonable size 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 late days. So please start early.
This homework focuses on reading and interpreting specifications, and reading and writing Java code. It also introduces using checkRep methods and testing strategies. You will implement some classes that 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.
Completing this homework requires knowledge of:
Before you get started, update your project src directory from your GitLab repository by using the git pull command. (There is also a git fetch command and others that sound like they might be useful . However, be sure to use git pull so you do not leave your repository in a strange state.) Once you have done that, work through the problems below. For this first problem, you only need to provide written answers. Edit the file hw4/answers.txt and put your answers there.
For this problem you will write pseudocode algorithms for arithmetic operations applied to single-variable polynomial equations. We provide an example for polynomial addition below.
You may use ordinary arithmetic operations on individual terms of polynomial equations without defining them yourself. 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:
RatPoly's div method:
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.Division of polynomials is defined as follows:
Given two polynomials u and v, with v != "0", 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 "u / v" returns q as defined above.
The following are examples of div's behavior:
- (x^3-2*x+3) / (3*x^2) = 1/3*x (with r = "-2*x+3").
- (x^2+2*x+15) / (2*x^3) = 0 (with r = "x^2+2*x+15").
- (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.
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):
(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). You will learn about immutable objects as you progress on this homework.)
You can dispense with italics, and you can represent "tp" as "t_p", for example.
Work through problems 1-5 below, using
the provided Specifications to help you
fill in the missing methods. You should have already updated your local files using git pull to get the hw4 starter files from your GitLab repository.
Problem 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 over 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 file hw4/answers.txt. 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.
// Rep Invariant for every RatNum r: ( r.denom >= 0 )
List the method or constructor implementations that would have to change. For each changed piece of code, describe the changes informally, and indicate how much more or less complex (in terms of code clarity and/or execution efficiency) the result would be. Note that the new implementations must still adhere to the given spec; in particular, RatNum.toString() needs to output fractions in reduced form.
return new RatNum ( numerExpr ,
denomExpr);. Consider an implementation of the same methods
that instead end with:
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 (hint: look at the @requires and @modifies clauses, or lack thereof) and fail to meet the specifications of the RatNum class?
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 specification 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.
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 comment any code you write, as needed; please do not over-comment.
We have provided a checkRep method in RatTerm that tests whether or not a RatTerm instance violates the representation invariants. We highly recommend using checkRep where appropriate in the code you write. Think about the issues discussed in the last question of Problem 1 when deciding where to call checkRep.
One small caveat exists with checkRep when running your programs in Eclipse. By default, Eclipse will have assertions turned off, so assert statements will fail to raise AssertionExceptions. To fix this in Eclipse, go to Run » Run Configurations... and in the Arguments tab, add the flag -ea to VM Arguments. This will tell Eclipse to throw exceptions when an assert statement fails.
Additionally, we have provided a fairly rigorous test suite in RatTermTest.java. You can run the given test suite with JUnit to evaluate your progress and the correctness of your code.
Answer the following questions, writing your answers in the file hw4/answers.txt. Again keep your answers to 2-3 sentences.
RatTerm.toString() still
cannot produce a term with a zero coefficient (excluding 0).
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 would have to change. For each changed piece of code, describe the changes informally, and indicate how much more or less complex (in terms of code clarity and/or execution efficiency) the result would be. 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 RatTerm invariants (coeff.isNaN() ==> expt = 0; coeff.equals(RatNum.ZERO) ==> expt = 0; both; neither) do you prefer? Why?
Following the same procedure given in Problem 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). Since this problem depends on Problem 2, you should not begin it until you have completed Problem 2 (and the hw4.test.RatTermTest test suite runs without any errors).
You may also want to look at the specifications for the java.util.List class, especially the get(), add(), set(), and size() methods.
You are welcome to do what you like with the provided private helper methods in RatPoly (scaleCoeff and the like); 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 is given an accurate specification and is not still an unimplemented skeleton.
Make sure your code passes all the tests in RatPolyTest.java.
Following the same procedure given in Problem 2, 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 problem depends on Problems 2 and 3, you should not begin it until you have completed Problems 2 and 3 (and the hw4.test.RatTermTest and hw4.test.RatPolyTest test suites run without any errors).
Make sure your code passes all the tests in RatPolyStackTest.java.
Now that RatPoly and RatPolyStack are finished, you can run the calculator application. 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.
When you run hw4.CalculatorFrame, 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. The graph display will update on the fly, graphing the top four elements of the stack.
Submit your four favorite polynomial equations, in the RatPoly.toString format, in the file hw4/answers.txt.
The following classes are all provided for you. See the Javadoc specifications for how to use them.
By the end of the homework, you should have the following files committed and pushed to GitLab in your hw4 directory:
Be sure that your answers.txt file contains answers to all of the required questions and that you did not skip any.
When you have committed and pushed all of your changes and are done with the assignment, you should create a git tag in your repository named hw4-final and push that tag to your repository. Once you have committed and pushed that tag, your assignment has been submitted and the staff will grade the files in your repository that are labeled with that tag.
After you have pushed the hw4-final tag to your GitLab repository, remember to log on to attu, clone a fresh, new copy of your repository, use git checkout hw4-final to switch to your final version of the assignment, then run ant validate in the hw4 directory to check that all is well. (See the assignment submission handout for details; they are the same as for hw3, except for the tag name.) Delete this extra copy of the repository after running the validate step. If there are errors or missing files, go back to your regular Eclipse repository to fix the problems, commit/push any changes, and run the clone/validate step again on attu.
You are free to work from home, but remember final code must run correctly on attu. After your last commit and push, run ant validate on attu as a double-check.
If you're having trouble running JUnit tests in Eclipse, try running them from the command line. Instructions are in the Editing and Compiling handout.
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. We have also added a TODO: comment in each of these
methods. In Eclipse, the "Tasks" window will give you a list of all TODO:
comments, which will help you find and complete these methods.
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.
The provided test suites in this homework are the same ones we will use to grade your implementation; in later homeworks the staff will not provide such a thorough set of test cases to run on your implementations, but for this homework you can consider the provided set of tests rigorous enough that you do not need to write your own tests.
Division of rational polynomials is similar to long division as taught in grade school. We draw an example here: