Problem Set 1: Around the World

To get started,

1. Ask Didit to create a remote psets/ps1 repository for you on Athena.
2. Pull the repo from Athena using Git:

If you need a refresher on how to create, clone, and import your repository, see Problem Set 0.

The theme of this problem set is to build a toolbox of methods for working with geographic points of interest located with latitude and longitude. You can read the Javadoc documentation for all classes in the problem set, generated from the .java source files.

Since we are doing test-first programming, your workflow for each method should be (in this order)…

1. Study the specification of the method carefully.
2. Write JUnit tests for the method according to the spec.
3. Implement the method according to the spec.
4. Revise your implementation and improve your test cases until your implementation passes all your tests.

On Problem Set 0, we graded only your method implementations. On this problem set, we will also grade the tests you write. In particular:

• Your test cases should be chosen using the input/output-space partitioning approach. This approach is explained in the reading about testing.
• Include a comment at the top of each test suite class describing your testing strategy – how you partitioned the input/output space of each method, and then how you decided which test cases to choose for each partition.
• Your test cases should be small and well-chosen. Don’t use a large set of data for each test. Instead, create inputs carefully chosen to test the partition you’re trying to test.
• Your tests should find bugs. We will grade your test cases in part by running them against buggy implementations and seeing if your tests catch the bugs. So consider ways an implementation might inadvertently fail to meet the spec, and choose tests that will expose those bugs.
• Your tests must be legal clients of the spec. We will also run your test cases against legal, variant implementations that still strictly satisfy the specs, and your test cases should not complain for these good implementations. That means that your test cases can’t make extra assumptions that are only true for your own implementation.
• Put each test case in its own JUnit method. This will be far more useful than a single large test method, since it pinpoints where the problem areas lie in the implementation.
• Again, keep your tests small. Don’t use unreasonable amounts of resources (such as MAX_INT size lists). We won’t expect your test suite to catch bugs related to running out of resources; every program fails when it runs out of resources.

You should also keep in mind these facts from the readings and classes about specifications (part 1, part 2):

• Preconditions. Some of the specs have preconditions, e.g. “this value must be positive” or “this list must be nonempty”. When preconditions are violated, the behavior of the method is completely unspecified. It may return a reasonable value, return an unreasonable value, throw an unchecked exception, display a picture of a cat, crash your computer, etc., etc., etc. In the tests you write, do not use inputs that don’t meet the method’s preconditions. In the implementations you write, you may do whatever you like if a precondition is violated. Note that if the specification indicates a particular exception should be thrown for some class of invalid inputs, that is a postcondition, not a precondition, and you do need to implement and test that behavior.
• Underdetermined postconditions. Some of the specs have underdetermined postconditions, allowing a range of behavior. When you’re implementing such a method, the exact behavior of your method within that range is up to you to decide. When you’re writing a test case for the method, you must allow the implementation you’re testing to have the full range of variation, because otherwise your test case is not a legal client of the spec as required above.

Finally, in order for your overall program to meet the specification of this problem set, you are required to keep some things unchanged:

• Don’t change these classes at all: the classes Angle, CardinalDirection, and PointOfInterest should not be modified at all.
• Don’t change these class names: the classes Angular, Bounds, Mapping, AngularTest, BoundsTest, and MappingTest must use those names and remain in the geo package.
• Don’t change the method signatures and specifications: The public methods provided for you to implement in Angular, Bounds, Mapping must use the method signatures and the specifications that we provided.
• Don’t include illegal test cases: the tests you implement in AngularTest, BoundsTest, and MappingTest must respect the specifications that we provided for the methods you are testing.

Aside from these requirements, however, you are free to add new public and private methods and new public or private classes if you wish. In particular, if you wish to write test cases that test a stronger spec than we provide, you should put those tests in a separate JUnit test class, so that we don’t try to run them on staff implementations that only satisfy the weaker spec. We suggest naming those test classes MyAngularTest, MyBoundsTest, MyMappingTest, and we suggest putting them in the geo package in the test folder alongside the other JUnit test classes.

In this problem, you will test and implement the methods in Angular.java.

You’ll find Angular.java in the src folder, and a JUnit test class AngularTest.java in the test folder. Separating implementation code from test code is a common practice in development projects. It makes the implementation code easier to understand, uncluttered by tests, and easier to package up for release.

You can run Main.java to apply these methods to some example points of interest provided by the staff. (Main.java will not be used in grading, and you are free to edit it as you wish.)

Hints:

• These methods use the Angle class. You can play around with latitudes, longitudes, and displacements to understand Angle. There are also several cases where different angles can represent the same latitude or longitude.

• The postcondition of toDegrees() is underdetermined in an important way; the example test test­ToDegrees­Equator shows one way to account for this under­determination using JUnit’s assert­Equals with a delta.

• displacement() also has an underdetermined postcondition in some circumstances, which gives the implementor (you) more freedom and the client (also you, when you’re writing tests) less certainty about what it will return.

• For all problems on this problem set, you are free to rename, rewrite, replace, or remove the provided example tests and their assertions.

Commit to Git. Once you’re happy with your solution to this problem, commit and push! Committing frequently – whenever you’ve fixed a bug or added a working and tested feature – is a good way to use version control, and will be a good habit to have for your team projects.

In this problem, you will test and implement the methods in Bounds.java. The boundingBox() method creates latitude-longitude bounding rectangles as specified at the top of the file, and the inBoundingBox() method filters a set of points to only those inside a bounding rectangle.

Hints:

• Carefully partition and generate test cases for these specs before you start implementing! For boundingBox(), pay attention to the requirement that a smallest bounding box is returned, regardless of where the points are distributed around the globe.

• Writing small helper methods in your test classes can help DRY up the tests, make them easier to read, and prevent copy-and-paste bugs. For helper methods that you add to Bounds, be sure to write specs for them, and remember to test those methods in your own MyBoundsTest class, not in BoundsTest.

• Use the visualizing latitudes, longitudes, and displacements page.

• For all problems on this problem set, you are free to rename, rewrite, replace, or remove the provided example tests and their assertions.

Commit to Git. Once you’re happy with your solution to this problem, commit and push!

In this problem, you will test and implement the methods in Mapping.java, which we could use to build useful maps from raw point-of-interest data.

Run Main.java to apply these methods to some example points of interest. Edit the file example-points.csv to add, remove, or change the examples.

In this problem, you will implement one additional kind of evidence in reduceDuplicates(). Many companies that provide mapping services do so by aggregating information from multiple sources, and de-duplicating the data is an important problem.

Here are some ideas for evidence of duplication. Feel free to experiment with your own.

• Similar location. Points of interest are not physically points, and different data sources might place them at slightly different locations. Relating latitude-longitude and physical location is complicated, since the earth is not a sphere, continents drift, etc. As a start, note that one second of longitude equals between 0 and about 100 feet, depending on latitude.

• Similar names. Names with small string edit distance might simply contain typos. Names with larger differences might still point to the same place, for example The Grind Café vs. Cafe Grind.

• Missing data. Many real-word systems use magic numbers for location when the exact position of a place is unknown. For example, the geographic center of a country or state if that’s all the data source knows; or 0°N 0°E if there’s no information at all.

Keep in mind that whatever additional evidence you implement, your reduceDuplicates() must still obey the spec. To test your specific implementation, make sure you put test cases in your own MyMappingTest class rather than the MappingTest class that we will run against staff implementations. Your work on this problem will be judged by the clarity of the code you wrote to implement it and the test cases you wrote to test it.

Make sure you commit AND push your work to your repository on Athena. We will use the state of your repository on Athena as of 10:00pm on the deadline date. When you git push, the continuous build system attempts to compile your code and run a subset of the autograder tests. You can always review your build results at didit.csail.mit.edu.

Didit feedback is provided on a best-effort basis:

• There is no guarantee that Didit tests will run within any particular timeframe, or at all. If you push code close to the deadline, the large number of submissions will slow the turnaround time before your code is examined.
• If you commit and push right before the deadline, the Didit build does not have to complete in order for that commit to be graded.
• Passing some or all of the public tests on Didit is no guarantee that you will pass the full battery of autograding tests — but failing them is almost sure to mean lost points on the problem set.