CSCI
2600 Principles of Software
As always, we recommend that you read the entire homework before you begin work. As always, you must commit and push to your git repository, then submit on Submitty.
Submission Instructions
• Follow the directions in the version control handout for cloning your git repo.
• Be sure to commit and push the files to Submitty. Follow the directions in the version control handout for adding and committing files.
• Be sure to add the problem1.pdf, problem2.pdf, problem3.pdf, collaboration.pdf, and reflection.pdf files to the answers folder in your repo in Eclipse using Team/Add to Index.
You MUST type up your answers. Handwritten solutions will not be accepted or graded,
even if they are scanned into a PDF file.
We recommend using LaTeX. If you have never
used LaTeX, take a look at this tutorial.
•
Important:
You must press the Grade
My Repository button, or your answers will not be graded.
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 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:
You should have files RatNum.java
and RatPoly.java in directory src/main/java/hw3/, and files RatNumTest.java, RatPolyTest.java and RatPolyDivideTest.java in directory src/test/java/hw3/. Read through the
specifications in RatNum.java
and RatPoly.java to help you
work through the problems below.
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 answers/problem1.pdf.
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.
public negate() {
this.numer = -1 * this.numer;return ;
}
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 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 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 running the entire suite at once.
Answer
the following questions, writing your answers in the file answers/problem2.pdf. Remember, keep your answers to 2-3
sentences.
Write a pseudocode algorithm for division. State the loop invariant for the main loop and prove partial correctness. Write your answer in the file answers/problem3.pdf
When writing pseudocode use symbols +,-,* and / to express rational number and polynomial arithmetic. You may also use u[i] to retrieve the coefficient at power i of polynomial u, as well as c*x^i to denote the single-term polynomial of degree i and coefficient c. Important: write your pseudocode, invariants and proofs first, then write the Java code. Going backwards will be harder.
Use the following definition
of polynomial division:
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 division'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 the proof question, you do
not need to handle division by zero; however, you will need to do so in the
Java program.
Next, complete the public method public RatPoly div(RatPoly) in 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 is true.
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.
Please answer the following questions in a file named collaboration.pdf in your answers/ directory.
The standard academic integrity policy applies to this homework. All submitted work must be your own.
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.
Please answer the following questions in a file named reflection.pdf 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 Principles of Software in the future.
Push to git the following files. Don't forget to submit in Submitty!
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.
The
provided test suites in this homework are the same ones we will use to grade
your implementation. In later homework assignments the staff will not provide
such a thorough set of test cases to run on your implementations. You will be
responsible for writing your test suites. 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 will be posted on the Submitty Discussion Forum.