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

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

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.


COS 226 Home Page
wayne@cs.princeton.edu
Last modified: February 3, 2004