COS 226 Programming Assignment Checklist: Pattern Recognition

Frequently Asked Questions

Do I really need to print out and draw a minimal subset of line segments? You should avoid including redundant line segments if there are never more than 4 collinear points. You will receive a small bonus if you avoid redundant line segments in Fast.java when there are 5 or more collinear points.

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.

Why use Math.atan2 instead of Math.atan? The latter treats the angle between the origin and (x, y) as equal to the angle between the origin and (-x, -y). For the collinearity test, it should work. But you cannot use atan blindly for compareTo since you could end up with inconsistent situations such as a < b and b < c, but a > c.

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 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.

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 read in the data and plot graphics? Use StdIn for reading from standard input and StdDraw for drawing. See Section 2.4 for a refresher.

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

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, StdDraw.java and Draw.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. Write a function in Point that takes a point p as an argument, and returns a Comparator that uses 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.