Handout P1

Quick links:

• Specifications: HTML Documentation, Starter code
• Provided source code
• Problem Set Submission

Contents:

• Introduction
• Problems
  • Problem 1: RatNum (24 points)
  • Problem 2: RatPoly (45 points)
  • Problem 3: RatPolyStack (30 points)
  • Problem 4: PolyCalc (1 point)
• Provided classes
• Getting started
  • Hints
• Errata
• Q & A

We recommend that you read the entire problem set before you begin work.

Introduction

To complete this problem set, you will need to know:

1. Basic algebra (rational and polynomial arithmetic)
2. How to read procedural specifications (requires, modifies, effects)
3. 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, then, else)
4. How to run a Java compiler such as javac to create .class files
5. How to run the Java Virtual Machine (JVM) such as java to execute both your code and staff-provided libraries

Problems

Problem 1: RatNum (24 points)

Answer the following questions, writing your answers in the file problem1.txt

1. What is the point of the one-line comments at the start of the add, sub, mul, and div methods?
2. Notice that 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?
3. RatNum.div(RatNum) checks whether its argument is NaN (not-a-number). RatNum.add(RatNum) and RatNum.mul(RatNum) do not do that. Explain.
4. Why is RatNum.parse(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?
5. In the code for RatNum.parse(String), there are three clauses for constructing the result value.  Which of the three use the 'slashLoc' variable defined in the first line of the method?  Give an alternate implementation (in the problem1.txt file) where 'slashLoc' is still defined just once, but at a different point in the control flow of the method, closer to its uses.  Why might one prefer the provided implementation?
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 were required to enforce the invariant on exit.  The new rep invariant would then be:

    // Rep Invariant for every RatNum r: ( r.denom >= 0 )

Which method or constructor implementations would have to change?  For each changed piece of code, describe the changes informally, and indicate how much more or less complex the result would be (both in terms of code clarity, and also in terms of execution efficiency). Note that the new implementations must still adhere to the given spec; in particular, RatNum.unparse() needs to output fractions in reduced form.

Problem 2: RatPoly (45 points)

Read through the provided skeletal implementation of RatPoly.java. The most significant parts of the provided file are the comments describing how you are to use the provided fields to implement this class.  The Rep. Invariant is an especially important comment to understand, because what invariants you define can have a drastic effect on which implementations will be legal for the methods of RatPoly.

Fill in an implementation for the methods in the spec of RatPoly.  You may define new private helper methods as you like; we have suggested a few ourselves, complete with specifications, but you are not obligated to use them. (The staff believes that doing so will drastically simplify your implementation, however).

We have provided a fairly rigorous test suite in RatPolyTest.java. You can run the given test suite with JUnit as you program and evaluate your progress and the correctness of your code.

The test suite depends heavily on the implementation of the RatPoly.unparse() method; if the test suite claims that all or many of the tests are failing, the source of the problem could be a bug in your implementation of unparse().

To run the RatPoly test suite, type the following command:

athena% java junit.swingui.TestRunner ps1.RatPolyTest

Problem 3: RatPolyStack (30 points)

We have provided a test suite in RatPolyStackTest.java. You can run the given test suite with JUnit as you program and evaluate your progress and the correctness of your code.

To run the RatPolyStack test suite, type the following command:

athena% java junit.swingui.TestRunner ps1.RatPolyStackTest

Problem 4: PolyCalc (1 point)

To run PolyCalc, type the following command:

athena% java ps1.PolyCalcFrame

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.unparse format, in the file problem4.txt.

Provided classes

The following classes are all provided for you, in compiled form, by the staff:

With source code also provided:

ps1.RatNum

ps1.RatNumTest

ps1.RatPolyTest

ps1.RatPolyStackTest

ps1.Cons (as part of the RatPolyStack.java starter code)

With source code not provided:

ps1.PublicTest

ps1.PolyGraph

ps1.PolyCalcFrame

ps1.RatTerm

ps1.RatTermVec

Getting started

Create a ps1 directory and copy the provided files to it:

mkdir ~/6.170/ps1

cp -p /mit/6.170/www/psets/ps1/ps1-spec/* ~/6.170/ps1

See the Specifications for the classes you will implement and those that are provided for you.

By the end of the problem set, you should have the following files ready to submit in your ps1 directory: problem1.txt, RatPoly.java, RatPolyStack.java, and problem4.txt, along with the Manifest file listing your submission entries.

Hints

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.

JUnit reloads all of your classes each time you run a test, so you don't need to restart the JUnit application after making changes to your Java code (though you do need to recompile your code for the changes to take effect).

For a non-graphical alternative method of running JUnit, use junit.textui.TestRunner instead of junit.swingui.TestRunner.

The provided test suites in problem set 1 are the same ones we will be using 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 tests.

Divison of polynomials over the rationals is similar to the long division that one learns in grade school. We draw an example of it here:

Errata

Tuesday, February 13, 2001

The 6.170 staff provided an implementation for the .parse(String) method of RatPoly. Unfortunately, our implementation had an error which broke the representation invariant stated at the top of the file. Specifically, the argument "0" caused a RatTerm of (0 . 0) to be created and added, which is incorrect. This bug might have caused the testParseSimple method of the RatPolyTest class to yield a failure.

We have now (as of 7:00pm) updated the starter file; if you had not yet begun the problem set, you may ignore this warning.

If you had already copied the starter file, you will need to make an edit to your ~/6.170/ps1/RatPoly.java file. At the end of the .parse(String) method, there is this block of code:

  // accumulate terms of polynomial in 'result'
  RatPoly termPoly = new RatPoly();
  termPoly.terms.addElement(new RatTerm(coeff, expt));
  result = result.add(termPoly);

Add an if test around the code, as follows:

  // accumulate terms of polynomial in 'result'
  if (!coeff.equals(new RatNum(0))) {
    RatPoly termPoly = new RatPoly();
    termPoly.terms.addElement(new RatTerm(coeff, expt));
    result = result.add(termPoly);
  }

This should fix the problem. Contact an LA or TA if you don't understand this change, or if you have further questions.

Q & A

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 rereading the problem set handout and the specifications) when you have a problem.

Thursday, February 15, 2001

Q: validate6170 isn't working even though my test cases pass! I'm getting: FATAL ERROR: Directory /mit/username/6.170/ps1 is not visible to system:6.170. Help! I want to turn my problem set in!

A: Don't panic! You just don't have your permissions set correctly, such that the staff won't be able to read your code. Type both of the following two commands, and try it again:

fs sa ~/6.170 system:6.170 read

fs sa ~/6.170/ps1 system:6.170 read

Wednesday, February 14, 2001

Q: What should RatPoly.eval() return on a RatPoly for which isNaN() is true?

A: The java.lang.Double class has a static final double called Double.NaN that represents NaN. That's what you should return in this case.

Tuesday, February 13, 2001

Q: Why does validate6170 complain about problem5.txt?

A: The original Manifest file we gave you mistakely listed this file as a requirement; it is not. You should edit your ~/6.170/ps1/Manifest file and remove the line which lists problem5.txt.

Q: Why doesn't the test driver check RatPoly.eval()?

A: It was accidentally omitted from the methods covered by the test suite. The test suite has since been updated and redeployed with new tests to check RatPoly.eval() and also if there are any obvious violations of the RatPoly immutability property. The addition of these tests has not changed the specification; if your code was correct before, it should pass the new test suite. The newer test suite is the one that we will be using to grade your code, and so we recommend that you make sure to run your implementation against this version of the test suite.

Monday, February 12, 2001

Q: Should RatPoly(0,n) make a "0" polynomial? How am I supposed to implement "0" polynomials? Can I represent it as a term with a zero coefficient?

A: Yes, RatPoly(0,n) should make a "0" polynomial. However, you can not create a term with a zero coefficient to represent it, because that would violate the representation invariant of RatPoly. You should carefully note the last sentence in the abstraction function of RatPoly: "If there are no terms, then the RatPoly represents the zero polynomial."

Q: But I don't get it.. Doesn't the rep. invariant say that terms can't be null? How can there be no terms, then?

A: Yes, but it can be empty. Please note that while the rep invariant states that the terms field itself cannot be null, you can have the terms field refer to a RatTermVec object that does not contain any terms. (This would lead to terms.size() returning 0.) Please talk to a TA if you're still confused about this point. (Please see the RatPoly code comments for the abstraction function and rep. invariant.)

Q: Why is the coeff argument to the RatPoly constructor an int instead of a RatNum?

A: This constructor is used by our test cases. We didn't provide another constructor which takes a RatNum for the coefficient because RatPoly.parse() is a more useful way of creating new RatPolys.

Q: What should I return for RatPoly.degree() when the RatPoly evals to NaN?

A: The degree of an NaN polynomial isn't defined. We've added a requires clause to RatPoly.degree(): "!this.isNaN()". Your method's behavior when the requires clause is violated can be arbitrary, i.e. you don't need to account for that case.

Q: What should my RatPoly.add(RatPoly p) method do when p is null?

A: We've added parameter != null requires clauses to a number of methods: sortedAdd, add, sub, mul, and div. Please see the updated spec.

Note: In the last two cases, you do not need to bother inserting the new requires clauses into your code if you've already begun coding; you can just act as if they were there. In fact, please be really careful not to overwrite your already (partially) implemented file with our unimplemented one!