COS 226 Programming Assignment Checklist: Pattern Recognition

Frequently Asked Questions

What's a checklist? The assignment checklists are meant to supplement the assignment, and clear up any confusing points. They will also provide brief hints on getting started. They also include links to sample data files, reference solutions, and readme template files. Be sure to read the checklist before each assignment.

Is there anything else I should do before getting started? Please read the Assignments Page, including the collaboration policy, lateness policy, and submission system instructions if you have not done so already. The programming assignments will require a good deal of time. The final source code may not be that long, but creating and debugging the code is a serious time commitment. It would be a mistake to wait until after Tuesday precept to start your assignments. You may be able to ask more meaningful questions in precept if you already have worked on the program enough to know what the real difficult issues are.

The whiteboard submission system describes my file as a C++ program instead of a Java program. Am I doing anything wrong? Unlikely. We use the Unix command file -b Point.java, and it occasionally gets it wrong because the language syntaxes are so similar.

Can I redraw the same line segment several times? Yes. If this simplifies your code, we'll allow it without penalty.

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 π? Use Math.PI.

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 it for compareTo since you could end up with inconsistent situations like 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 with c not equal to zero? Yes, I believe so. In any case, it's fine on this assignment to assume that they will since our main focus here is not floating point precision. In real applications, you would use the integer pseudo-angle trick described below.

Do I have to implement my own sorting algorithm? No, there is no need to re-invent the wheel. Feel free to use any code from lecture such as ArraySort.java or any code from the Sedgewick book with an appropriate reference. You may also use Java's system sort.

How do I measure the running time of my program in seconds from Unix, Linux or OS X?  Use the command:

/usr/bin/time java Hello < input.txt > output.txt

How do I measure the running time of my program in seconds from Windows?  The easiest solution is to use a stopwatch. A more complicated approach involves adding in some Java code (don't forget to remove it before submitting) as in Timing.java. If you use this, be sure that you are running on a lightly loaded system since it uses the system time to measure running time. Srivas Prasad '03 suggests chaing the command prompt to display the time using "prompt $t", creating a batch file with "cls" and "java Hello < input.txt > output.txt". The clear screen command clears the screen and displays the starting time in the prompt; upon termination the prompt shows the ending time. If you have a better solution, let us know.

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

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 Turtle.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 turtle graphics. The files Point.java and PointPlotter.java form a program that reads in a list of points and plots the results using Turtle graphics. You will need to have the helper programs Turtle.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. You can close the window by click the close window widget or typing Ctrl-c.

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.

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. However, the Comparable interface requires that you invoke the compareTo method with q1.compareTo(q2), so there is no opportunity to pass it p. There are three main approaches you can take to overcome this obstacle.

   • Perhaps the easiest (but not necessarily the best design) is to abandon the Comparable interface. Modify Sedgewick's sorting code so that it sorts Point objects instead of Comparable objects. Then modify all of the functions so that they take an extra Point argument p, which you can now use to make comparisons.

   • A more satisfying solution is to use Java's system sort or Sedgewick's sorting code with no modifications. Program Student.java from lecture illustrates how to implement a data type so that the client can change the sorting key.

     To do this, make Point.java implement the Comparable interface. Introduce a static variable (here, static means that it is a common variable, shared by the whole class) p to Point.java that represents the origin. Then, add a function

     public static void setOrigin(Point theOrigin)
     

     that sets the origin, and a method

     public int compareTo(Object q2)
     

     such that invoking q1.compareTo(q2) returns a negative integer, zero, or a positive integer depending on whether the angle that q1 makes with p is less than, equal to, or greater than the angle that q2 makes with p. The method compareTo now has access to the origin p, and the client can change p by calling setOrigin.

   • Yet another approach is to create a separate Comparator object each for each point p. Here's a reference. This is similar to the previous approach, exept that the point p is stored in a Comparator object instead of as a static variable in the Point class.

4. Bells and whistles. Here are two nice observations that can speed up your fast solution and earn you bonus points.

   • If four points p, q, r, and s are collinear, you only need to detect the line segment once, not four times. As a result, when examining point p, it's sufficient to only compare other points that are in the upper right or upper left quadrants relative to the origin p, i.e., all of the angles will be between 0 and 180 degrees. You might miss discovering a collinear group when examining p if p is not the bottom-most point in the group, but you'll discover it when examining one of q, r, or s.

   • To speed up your program further (and avoid precision issues with floating point numbers), use only integer arithmetic. You don't actually need to compute the angles that q1 and q2 make with p; what you really need is to be able to compare the angles that q1 and q2 make with p. You can do this by comparing (q1.x - p.x) (q2.y - p.y) with (q2.x - p.x) (q1.y - p.y). Note that by the previous trick, all points fall in the upper left or upper right quadrants so you don't need to worry about comparing points in opposite quadrants.

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.