Quick links:
Contents:
We recommend that you read the entire problem set before you begin work.
In this problem set, you will practice 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 problem set, you will need to know:
Problem 0 is due on Thursday, April 1, 2010, before the rest of the problem set is due. You should hand in problem 0 electronically by committing it to your repository before 8:30am; assignments received after that, or not received electronically, will be considered late. Problem 0 does not involve any Java programming and, therefore, does not involve any set-up. To start work on the rest of the problems (1-5), please follow these instructions.
Update the src directory in your SVN repository. Then, work through the problems below. Use the provided Specifications to help you fill in the missing methods.
By the end of the problem set, you should have the following files committed to SVN in your ps1 directory:
You are free to work from home, but keep in mind that your final code MUST run correctly 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.
This problem is due before the rest of the problem set. You will receive feedback for this problem from your TA before the final problem set due date.
For this problem you write pseudocode algorithms for arithmetic operations applied to single-variable polynomial equations. We provide an example for polynomial addition below.
You may use arithmetic operations on terms of polynomial equations as primitives. 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.
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. You will learn about immutable objects as you progress on this problem set.)
Record your answers to this problem in the file ps1/answers/problem0.txt.
Read the specifications for RatNum, a class representing rational numbers. Then read over the staff-provided implementation, RatNum.java.
You may find it helpful to peruse 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 ps1/answers/problem1.txt:
// Rep Invariant for every RatNum r: ( r.denom >= 0 )
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, 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. Make sure that 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.
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() 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 ps1/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?
Follow the same procedure given in Problem 2, and read over the specifications for the RatPoly class and its methods, and time 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 ps1.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.
Follow the same procedure given in Problem 2, , and 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 ps1.test.RatTermTest and ps1.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 ps1.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 ps1/answers/problem5.txt.
Daikon is a software engineering tool that reports properties about programs similar to representation invariants and method pre- and postconditions. Please read the introduction to Daikon.
For this problem, you will generate and analyze the results of running Daikon on the RatNum class using two different test suites: RatNumTest, the original test suite, and RatNumSmallTest, a reduced test suite that does not provide as much coverage.
To ease your work, we have provided you with ant targets to run Daikon with the correct arguments for this particular problem. Like most of the other targets (e.g. "build"), these targets can be run from either Eclipse or the command line.
First, run Daikon from your ps1 directory using the original RatNum test suite (RatNumTest):
ant daikon-RatNumTest
This command will place Daikon's results in daikon-RatNumTest.inv.txt in your ps1 directory. If you are using Eclipse, you will need to refresh the ps1 directory to see the results file in the Package Browser.
Next, run Daikon on the reduced RatNum test suite (RatNumSmallTest):
ant daikon-RatNumSmallTest
This command will place Daikon's results in daikon-RatNumSmallTest.inv.txt in the ps1 directory. If you are using Eclipse, you will need to refresh the ps1 directory to see the results file in the Package Browser.
Please answer the following questions in the file ps1/answers/problem6.txt:
Please answer the following questions in a file named collaboration.txt in your ps1/answers/ directory.
The standard collaboration policy applies to this problem set.
State whether or not you collaborated with other students. If you did collaborate with other students, put their names and a brief description of how you collaborated.
Please answer the following questions in a file named reflection.txt in your ps1/answers/ directory.
After you receive your corrected problem set back from your TA, you will have until 8pm, April 26 before you have to resubmit it electronically by committing the problem set to your repository and then running returnin331. Returnin will be enabled on 8pm, April 19 for problem set 1.
You will only receive credit if you pass all the tests, and you have a fixed number of trials without penalty. See the returnin331 documentation for details.
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:
If you're having trouble, the Forums are a good place to look for help.
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 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:
None yet
This section will list clarifications and answers to common questions about problem sets. We'll try to keep it as up-to-date as possible, so this should be the first place to look (after carefully re-reading the problem set handout and the specifications) when you have a problem.