6.170 / Spring 2000 / Problem Set 3 Amendments

6.170

Laboratory in Software Engineering
Spring 2000
Amendments to Problem Set 3
Due: February 24, 2000
Handout 9

General Amendments/Clarifications:

If any of the Iterators your methods return expose the internal representation of your object to the user, you will lose credit. If you discover a shortcut in implementing methods that return Iterators, you must ensure that it is a correct shortcut.

This is an important issue: exposing the representation is not just something that happens when you write the spec (though that is a place where it can occur). Giving the user the ability to alter the internal structure of your object without using the mutator operations that you provide is also considered exposing the representation. Please note that the default JDK-style Iterator provides a remove() operation that actually changes the state of the data structure that the Iterator is traversing. The Iterator abstraction used in 6.170 does not provide this operation (thus it is not mentioned in the text). This is why we have given you the UnmodifiableIterator class to use in your implementations: by extending the class and using the default implementation of remove() that UnmodifiableIterator provides, you can ensure that the Iterator you are making does not allow access to the underlying state.

The location of the implementation of UnmodifiableIterator was accidentally omitted from the problem set; it is available in /mit/6.170/src/ps3/UnmodifiableIterator.java . Again, you are not required to use the UnmodifiableIterator class, but it helps if you are trying to be consistent with the Iterator abstraction as presented in the Liskov text.
You no longer are required to hand in your test-driver implementations for Table and DiGraph. However, this means that even more weight will be placed on the writeup that you make for the client: make sure that it is clear, straightforward, and covers all of the tests that you chose to implement. If you do not have time to implement all of the tests that you feel you needed for validation, seperately describe the tests that you did not get a chance to implement in your documentation.
You are still required to include the output from running your test-driver in your writeup. Please try to make the output somewhat sane in its descriptions of the different tests that are run. Fifty lines that just say "Test 1: Ok; Test 2: Ok; Test 3: FAILED ..." are not considered as nice as output that gives a concise description of the functionality checked by each test. Some tests may be too complex to describe completely without taking up inordinate space in the output. In that case, the output should include an abbreviation for the functionality that is being tested, and then the abbreviation (and the details of the associated test) should be documented in your writeup with the rest of the test case descriptions.
When writing your Test Drivers for Problems 2 and 4, you may use implementations of java.util.Set to test your Iterators. You may not need to, but be wary of being overly strict in your testing and flagging valid implementations of Table and DiGraph as flawed. If you are wondering why you may need to use a set abstraction to test an Iterator, reread Appendix D, specifically the part defining a complete traversal.

Problem 1 Amendments/Clarifications:

It is no longer required that you implement the similar operation in Table to run in linear time. The conditions given in Appendix D for evaluating similarity could actually take O(n²) time, depending on your own implementation of Table's methods; this is an acceptable time bound for this operation. However, the other operations still should take no more than linear time, as described in the problem set; this amendment is only excepting the similar operation from the linear time bound.
The values returned by the Table.lookup method are intended to allow mutation. Allowing the user to change the data stored in a Table's value object is not considered to be exposing the rep of the Table; indeed, it is intended to be a possible use of the Table abstraction. An example of this usage would be a Table that associates Integer objects with DiGraph objects: the Integers are immutable, but the DiGraphs are mutable. The user should have to work with the Table to change which DiGraph is associated with a particular Integer, but changing the state of a particular DiGraph should not affect the Table at all. So if you find yourself wondering if you should call clone() on the Objects that you are returning from Table.lookup, you are misinterpreting what the purpose of the Table is.

Problem 3 Amendments/Clarifications:

You are expected to implement DiGraph using the Table object. If you absolutely cannot figure out how to implement DiGraph using Table, but you can do it using some other way, (such as making a variant of Table or using one of the classes in the java.util package), then you should do that instead of handing in nothing for your implementation, but you will not get as many points as someone who implemented it using a Table. If you think that it is impossible to satisfy the specification of DiGraph using just the provided Table abstraction, you either:

misunderstand some aspect of the specification for Table
have not considered all of the ways that you can use the provided Table abstraction to implement the specification of DiGraph.

Problem 5 Amendments/Clarifications:

The problem set originally only asked for you to document the changes that you did make to the specifications given. We would also like for you to seperately document changes that you would have liked to have made, but could not because you were restricted to only strengthening the specification. Specifically, if you feel that the specified behavior of a method is not what should "intuitively" happen for some situation, or if you felt that some particular functionality was missing from the methods provided by the specifications, then document that in your writeup so that the client may evaluate if the specification should in fact be changed.
This writeup is probably the most important part of the problem set. Some of you have just been handing in code listings for the previous problem sets: while that's great for the Java Runtime, most people are much better at reading human languages like English.