Quick links:
Contents:
As always, we recommend that you read the entire homework before you begin work. It's long but it's in reasonable size chunks.
This homework focuses on reading and interpreting specifications, and reading and writing Java source code. Additionally, you will be given an introduction to using checkRep methods and testing strategies. You will implement three 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.
To complete this homework, you will need to know:
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 within your algorithms for subtraction, 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.
For this first problem you don't have to write any 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:
// 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);. 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 function (Hint: take a look at the @requires and @modifies statements, or lack thereof.) and fail to meet the specifications of the RatNum class?
Read over the specifications for the RatTerm class, making sure you understand the overview for RatTerm and the specifications for the given methods.
Read through 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.
For all of 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 you use checkRep() where appropriate in the code you write. Think about the issues discussed in the last question of problem 1 when deciding where checkRep should be called.
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:
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. Which method or constructor implementations would have to change? Please list them. 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 take a 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 private helper methods that we give you 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 functions. However, you must make sure that every private helper function in the final version of the class has 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. Take a look at the Javadoc specifications for more information on how to use them.
With source code provided:
You are free to work from home, but keep in mind that your final code must run correctly on the lab machines (we'll test it on attu). Once everything is in order, make sure you've committed your changes. You should also run ant validate on attu as a double-check.
By the end of the homework, you should have the following files committed to SVN in your hw4 directory:
Don't forget to use the forum.
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 of the unfinished methods in RatTerm, RatPoly and RatPolyStack throw
RuntimeExceptions.
When you implement a method, you should be sure to
remove the throw new RuntimeException(); statement. For those of you who
use Eclipse, we have also added a TODO: comment in each of these
methods. 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 to be rigorous enough that you do not need to write your own tests.
Division of polynomials over the rationals is similar to the long division that one learns in grade school. We draw an example of it here:
None yet.
None yet.