Description

As always, we recommend that you read the entire homework before you begin work. As always, you must commit to your SVN repository, then submit through the Homework server.

Introduction

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 one class that will complete the implementation of a polynomial with rational coefficients, 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:

1. Basic algebra (rational and polynomial arithmetic) and polynomial arithmetic
2. How to read and write basic Java code
   • code structure and layout (class and method definition, field and variable declaration)
   • method calls
   • operators for:
     • object creation: new
     • field and method access: .
     • assignment: =
     • comparison: ==, !=, <, >, ≤, ≥
     • arithmetic: +, -, *, /
   • control structure: loops (while and for) and conditional branches (if, else)
3. How to read procedural specifications in the PoS convention (requires, modifies, effects, returns and throws)

Problems

You should have files RatNum.java and RatPoly.java in directory hw3, and files RatNumTest.java, RatPolyTest.java and RatPolyDivideTest.java in directory hw3.test. (RatPolyDivideTest.java is only needed for the extra credit problem which asks for polynomial division. It shows errors because the division operation has not been added yet to RatPoly.java.) Read through the spcifications in RatNum.java and RatPoly.java to help you work through the problems below.

Problem 1: RatNum (5pts)

For this first problem you don’t have to write any code, but you do have to answer written questions. Read the specifications and provided implementation in RatNum.java, a class representing rational numbers.

You may 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 hw3/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. Points will be deducted for answers that are excessively long or contain irrelevant information.

1. Classify each public method of RatNum as a creator, observer, producer or mutator.
2. What is the point of the one-line comments inside the add, sub, mul, and div methods?
3. 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?
4. RatNum.div(RatNum) checks whether its argument is NaN (not-a-number). RatNum.add(RatNum) and RatNum.mul(RatNum) do not do that. Explain.
5. 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?
6. 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 would 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 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.

7. 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?

8. 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: RatPoly (45pts: Code: 40pts autograded, Answers: 5pts)

Read over the specifications for the RatPoly class, making sure you understand the overview for RatPoly and the specifications for the given methods. Read through the provided skeletal implementation of RatPoly.java.

Fill in an implementation for all methods.

You may define new private helper methods as you like. You may not add public methods; the external interface must remain the same. (If you implement the Extra credit question you will have to add one specific public method.) 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 RatPoly that tests whether or not a RatPoly 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.

There is a fairly rigorous test suite in RatPolyTest.java. You can run the given test suite with JUnit to evaluate your progress and the correctness of your code. It is probably a good idea to run tests individually rather than runnning the entire suite at once.

Answer the following questions, writing your answers in the file hw3/answers/problem2.txt. Remember, keep your answers to 2-3 sentences.

1. We have chosen the array representation of a polynomial: RatNum[] coeffs, where coeffs[i] stores the coefficient of the term of exponent i. An alternative data representation is the list-of-terms representation: List<Term> terms, where each Term object stores the term’s RatNum coefficient and integer exponent. The beauty of the ADT methodology is that we can switch from one representation to the other without affecting the clients of our RatPoly! Briefly list the advantages and disadvantages of the array representation versus the list-of-terms representation.
2. 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?
3. Imagine that the representation invariant of RatPoly was weakened so that we did not require the last element of coeffs to be non-0. 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 will 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.

Problem 3: Polynomial division (10pts EXTRA CREDIT: Pseudocode and invariant: 5pts, Java code: 5pts autograded)

Write a pseudocode algorithm for division. State the loop invariant for the main loop. You do not need to prove partial correctness, just give the right invariant. Write your answer in the file hw3/answers/problem3.txt.

The following is the definition of polynomial division:

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.

For this question, you do not need to handle division by zero; however, you will need to do so for the Java programming exercise.

Next, add a public method public RatPoly div(RatPoly p) with appropriate specification to the RatPoly class and transfer your pseudocode algorithm into div. You may assume that the divisor p is non-null. If p is zero div returns some q such that q.isNaN. As with the other operations (e.g., mul), if this.isNaN or p.isNaN, div returns some q such that q.isNaN.

There is an extensive test suite for division in RatPolyDivideTest.java. You can run this test suite to evaluate your progress and the correctness of your code.

Collaboration

Please answer the following questions in a file named collaboration.txt in your answers/ directory.

The standard academic integrity policy applies to this homework.

State whether or not you collaborated with other students. If you did collaborate with other students, state their names and a brief description of how you collaborated.

Reflection

Please answer the following questions in a file named reflection.txt in your answers/ directory. Answer briefly, but in enough detail to help you improve your own practice via introspection and to enable the course staff to improve PoS in the future.

1. In retrospect, what could you have done better to reduce the time you spent solving this homework?
2. What could the PoS staff have done better to improve your learning experience in this homework?
3. What do you know now that you wish you had known before beginning the homework?

What to submit

By the end of the homework, you should have the following files committed to SVN in your hw3 directory:

• answers/problem1.txt
• answers/problem2.txt
• answers/problem3.txt(Extra credit)
• RatPoly.java
• answers/collaboration.txt
• answers/reflection.txt

All of the unfinished methods in RatPoly 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. Fortunately, you did write pseudocode for most of the polynomial arithmetic algorithms in Homework 2.

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.

Errata

None yet. Check the Announcements page regularly.

Q & A

None yet.