### COS 226 Programming Assignment Checklist: Pattern Recognition

How should I read from standard input? Write to standard draw? In this course you will use our home-brewed library StdIn.java to read text from standard input and library StdDraw.java to plot graphics on standard draw. For those of you that didn't take COS 126, read Section 1.5 of Introduction to Programming to learn how to use them.

Do I really need to print out and draw a minimal subset of line segments? You should avoid printing overlapping line segments if there are never more than 4 collinear points, e.g., if p2 and p3 are on the line segment p1p4, print out either p1p4 or p4p1, but don't print out p1p3 or any other sub-segment. You will receive a small bonus if you avoid overlapping line segments in Fast.java when there are 5 or more collinear points, e.g., p2, p3, and p4 are on the line segment p1p5, print out either p1p5 or p5p1, but don't print out p1p4 or any other sub-segment.

Can the same point appear more than once in the input file? No. 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.

Do I have to implement my own sorting algorithm? No, use Java's system sort Arrays.sort().

Can I sort just part of an array? Sure. 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 or 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.

How do I measure the running time of my program in seconds?   Either use StopWatch.java as in lecture. It's probably a good idea to redirect output to a file so that you avoid counting the time needed to display the text on the screen.

If you use Linux or OS X, you can use the following command instead:

/usr/bin/time java Hello < input.txt > output.txt
and look at the output for user time. Note that you should use the full path name; otherwise your shell might use its own built-in time command. Be careful when using /usr/bin/time with piping - it may only time the first process and not the whole chain.

How do I profile my program? Execute with the command

java -Xprof Hello < input.txt > output.txt

 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 lines to your system. It contains a number of sample input files and some helper programs. If you're using arizona, you can directly access the files via the path ~cos226/ftp/lines/ and avoid using up your quota. Reacquaint yourself with StdDraw. The files Point.java and PointPlotter.java comprise a program that reads in a list of points and plots the results. You will need to have the helper programs StdDraw.java, Draw.java, and StdIn.java in your working directory. 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. Include a public and final instance variable BY_POLAR_ORDER in Point that is a Comparator<Point> that uses the invoking Point p as the origin.

 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.

wayne@cs.princeton.edu