| |
|
Homework 3: Java and Coding to Specifications
Due: Tuesday, Jan. 31, 2012 at 11pm
In this assignment, you will complete the implementation of a graphing polynomial calculator. You will practice reading and interpreting specifications and reading and writing Java source code. You will also be introduced to using checkRep methods and testing strategies.
You should be comfortable with the basic notions of polynomial numbers and rational numbers for this assignment.
Errata
Disregard the reference to problem 6 in the turning instructions. Problem 6 is a lie. There is no problem 6!
Setup
- Create a new Eclipse project named
HW3.
- Download the project source code as hw3.zip. Anywhere we direct you to a .java file below, refer to the files in hw3.zip.
- Unzip hw3.zip. Inside are two directories:
calculator and test. These are packages for organizing your code. Copy these two packages (using the basic file system copy command), then go to Package Explorer in Eclipse and paste them into HW3/src. (Alternatively, you can copy them over outside of Eclipse simply by sticking them in <pathToYourWorkspace>/workspace331/HW3/src and hitting right-click >> Refresh or F5 in Package Explorer.)
- You may see errors in the
test package. You need to tell Eclipse to link in the Junit 4 library when compiling. In Package Explorer, right-click HW3 and choose Build Path >> Add Libraries... >> JUnit. Change the JUnit library version from JUnit 3 to JUnit 4 and click Finish.
Problem 0: Polynomial arithmetic algorithm (7 points)
For this problem you write pseudocode algorithms for single-variable polynomial arithmetic operations. Each operand is a polynomial number, and all operands are defined in terms of the same variable. For example, in the algorithm below, we might have p = x2 + 2x + 5 and q = 3x3 (but not p=2xy or p=2x and q=2y).
Here is an example of an algorithm for polynomial addition:
- r = p + q:
- set r = q by making a term-by-term copy of all terms in q to r
- foreach 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. 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 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:
- Write a pseudocode algorithm for subtraction.
- Write a pseudocode algorithm for multiplication.
- Write a pseudocode algorithm for division, as defined in the specification for
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.
-
Illustrate your division algorithm on these two examples:
- (x^3-2*x+3) / (3*x^2) = 1/3*x
- (x^3+x-1) / (x+1) = x^2-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 (2x^2 + 5) + (3x^2 - 4x):
- p = (2x^2 + 5)
- q = (3x^2 - 4x)
- r = copy of q = (3x^2 - 4x)
- foreach term, t_p, in p
- Iteration 1: t_p = 2x^2, r = (3x^2 - 4x), p = (2x^2 + 5), q = (3x^2 - 4x)
- [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]
- Iteration 2: t_p = 5, r = (5x^2 - 4x), p = (2x^2 + 5), q = (3x^2 - 4x)
- [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)
- We are done! 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).
You will learn about immutable objects as you progress on
this homework.)
Record your answers to this problem in the file answers.txt. (Note: we will also accept other standard file formats, but either txt or pdf is strongly preferred.)
Problem 1: RatNum (26 points)
Read the specifications for RatNum,
a class representing rational numbers. Then read over the provided
implementation, RatNum.java (located in the hw3.zip, which you downloaded earlier).
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 answers.txt:
-
What is the point of the one-line comments inside the
add, sub,
mul, and div methods?
-
add, sub, mul, and div all require that "arg != null".
This is because all of the methods access fields of 'arg' without checking
if 'arg' is null first. But the methods also access fields of 'this'
without checking for null; why is "this != null" absent from the requires-clause
for the methods?
-
RatNum.div(RatNum) checks whether its argument is NaN
(not-a-number). RatNum.add(RatNum) and
RatNum.mul(RatNum) do not do that. Explain.
-
Why is RatNum.valueOf(String) a static method? What alternative to
static methods would allow one to accomplish the same goal of generating
a RatNum from an input String?
-
Imagine that the representation invariant were weakened so that we 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 no longer were 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 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.
- 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 function (Hint: take a look at the @requires and
@modifies statements, or lack thereof.) and fail to meet the
specifications of the RatNum class?
- Calls to checkRep are supposed to catch violations in
the classes' invariants. In general, it is recommended that one 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?)
Problem 2: RatTerm (30 points)
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 in answers.txt:
-
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?
- Imagine that the representation invariant was weakened 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.
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; in particular,
RatTerm.toString() still
cannot produce a term with a zero coefficient (excluding 0).
- In the case of the zero RatTerm, we require all
instances to 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. 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?
Problem 3: RatPoly (45 points)
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 RatTermTest 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.
Problem 4: RatPolyStack (20 points)
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 RatTermTest and RatPolyTest run without any errors).
Make sure your code passes all the tests in RatPolyStackTest.java.
Problem 5: CalculatorFrame (1 point)
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 calculator.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 answers.txt.
Hints
- 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 and TODO: comment. 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 problem set 1 are the same ones we will
use to grade your implementation; in later problem sets the staff
will not provide such a thorough set of test cases to run on your
implementations, but for this problem set 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:
Turnin
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).
You should submit the following files to the dropbox:
- answers.txt, containing your answers to the problems in parts 0, 1, 2, and 5. Other file formats are also acceptable, but either txt or pdf is strongly preferred.
- RatTerm.java
- RatPoly.java
- RatPolyStack.java
Include your first and last name in every file. For source code, use the @author tag for this purpose. Your classes should be in the calculator package - in other words, please don't remove the package calculator; line at the top of each class.
|
CSE Home 