COS 226 Programming Assignment Checklist: Pattern Recognition

Frequently Asked Questions

Can the same point appear more than once in the input file? You may assume the data has been pre-processed so that this does not happen.

How do I access the mathematical constant π? It's Math.PI, but don't use it or you'll likely encounter floating point roundoff issues.

What's the difference between Math.atan2() and Math.atan()? The former returns an angle between -pi and pi; the latter returns an angle between -pi/2 and pi/2: it treats the angle between the origin and (x, y) as equal to the angle between the origin and (-x, -y). If you want to sort by polar angle, you should use atan2(). However, you might be happy sorting by something other than polar angle.

Does (Math.atan2(y, x) == Math.atan2(c*y, c*x)) if x, y, and c are integers between 0 and 32,768 with c not equal to zero? Yes, although this fact is probably not obvious without an understanding of IEEE floating point arithmetic.

How do I sort a subarray? Arrays.sort(a, from, to) sorts the subarray from a[from] to a[to-1] according to the natural order of a[]. Use a Comparator as the fourth argument to sort according to an alternate order.

How much extra space can I use?   Limit yourself to a constant amount of extra space for Brute.java and a linear amount of extra space for Fast.java. By extra space, we mean beyond the space needed to store the array of points.

Where can I see examples of Comparable and Comparator? See the lecture notes and Section 3.5 of the booksite. We assume this is new Java material for most of you, so don't hesitate to ask if you are unsure of how to use it.

Testing and Submitting

Input.   Here are some sample input files. Thanks to Jesse Levinson '05 for the remarkable input file rs1423.txt. To estimate the running time as a function of N, you may use the program Generator.java. It takes a command-line argument N and outputs a random instance of N points.

Reference solutions.   Some of the input files have associated .png files that contain the desired output. You can use these for checking your work.

Submission.   Your two programs must be named Brute.java and Fast.java. Both programs must use a common point data type named Point.java. Be sure to submit every file that your program needs (except StdIn.java and StdDraw.java). Don't forget to hit the "Run Script" button on the submission system to test that it compiles cleanly.

Readme.   Use the following readme file template and answer all questions. This includes analyzing the two algorithms both empirically and analytically.

Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps.

1. Getting started. Download the directory patterns to your system. It contains a number of sample input files and some helper programs. To download all the files at once:

   • Safari. Click the ftp link above to mount the ftp site, then drag-and-drop the nbody folder from the ftp mount to the desired location.

   • Internet Explorer. Click the ftp link above, then right click the nbody folder, select Copy To Folder, and choose the desired location.

   • Firefox. Install the extension DownThemAll! and use that to download all links from a given page.

   The files Point.java and PointPlotter.java comprise a program that reads in a list of points and plots the results. To plot the points, type the following at the command line

   javac PointPlotter.java
   java PointPlotter < input56.txt
   

   This should open up a graphical window where you will see the points plotted.

2. Brute force. Before writing any code, think carefully about the point data type operations that you will need to support. A minimalistic approach might involve creating a function

   public static double angle(Point a, Point b)
   

   that returns the angle that that b makes with a. The Java function Math.atan2(double y, double x) is exactly what you need: it returns the polar angle that corresponds to the point (x, y) in Cartesian coordinates. Then, use this helper function to create a function

   public static boolean areCollinear(Point a, Point b, Point c)
   

   that returns true if a, b, and c are collinear and false otherwise. Also consider a 4-argument version.

   public static boolean areCollinear(Point a, Point b, Point c, Point d)
   

3. Sorting solution. Before writing any code, think carefully about the point data type operations that you will need to support. The complicating issue is that the function needed to compare the angles of two points q1 and q2 depends on a third point p, which changes from sort to sort. One solution is to include a public and final (but not static) instance variable BY_POLAR_ORDER in Point of type Comparator<Point>. This Comparator has a compare() method so that compare(q1, q2) compares the angle that q1 and q2 make with the invoking object p.

Enrichment

This problem belongs to a group of problems that are known as 3SUM-hard. It is conjectured that such problems have no subquadratic algorithms. Thus, the sorting algorithm presented above is about the best we can hope for (unless the conjecture is wrong). Under a restricted decision tree model of computation, Erickson proved that the conjecture is true.