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 source 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:
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.
Problems 1-5 require some setup. Specifically, Update the src directory in your SVN repository. Then, work through the problems below, using the provided Specifications to help you fill in the missing methods.
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/problem1.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.
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/problem2.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/problem5.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 to SVN in your hw4 directory:
You are free to work from home, but remember final code must run correctly on attu. After your last commit, 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: