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

Platform: You may write, debug and test your program on any machine you like, but we will compile and run it on arizona which is a Sun Sparc machine. So it is recommended to check that it compiles and works there before wrapping up and submitting. Use the script gcc226 for compilation, it is a front end of the standard gcc compiler using certain options. The full path is /u/cs226/bin/gcc226 (on arizona). You can get a lab TA to help you add /u/cs226/bin to your path. Linux and OS X users can use essentially the same gcc226 script. Ask if you experience problems. After electronically submitting all the required files, a "Run Script" button will appear on the submission web page. Clicking this button will compile your files on a Sun Sparc machine using a script written especially for the assignment. You will see the output of the gcc226 compilation on the web page. Make sure no compilation warnings are generated.

When compiling turtle.c I get errors about the math library. How do I fix this? Use gcc226 or add the flag -lm to the end of your compilation command to help the linker find the math library.

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.

Do I have to implement my own sorting algorithm? No. Feel free to use (and change) quicksort.c or any other code from the Sedgewick book.

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

/usr/bin/time a.out < 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. Or, use our timeit.csh script to automate things.

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 C code (don't forget to remove it before submitting) as in timing.c. Srivas Prasad '03 suggests changing the command prompt to display the time using "prompt $t", creating a batch file with "cls" and "brute.exe < 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.

Files

Input. Here are some sample input files (those with ".txt" suffix). You can use generator.c to create random instances of N points in the plane by calling it with the command line parameter N. This is useful for estimating the running time as a function of N.

Be sure to enjoy the latest data file rs1423.txt, brought to you by Jesse.

Submission. Your submission must include the code files brute.c, lines.c, point.c and point.h. You may submit any other .c or .h files used in your project. Do not submit a Makefile. Assume all the files are kept in a flat directory (don't use directory paths while #includeing your .h files). brute.c and lines.c must both include a main() function. We will compile your project twice: in the first time we will include all the .c files except lines.c, and in the second time we will include all the .c files except brute.c. You are required to practice good modular design. Don't forget to hit the "Run Script" button on the submission system to test that it compiles cleanly. Other than C code files, you must submit a readme.txt file (explained below).

Reference solutions. For reference, we provide our executable code on Windows, Solaris, and OS X.

readme.txt

Use the following readme file template. Besides providing details about your implementation which are not clear from the comments within your source code, your readme.txt file should also:

Analyze the two algorithms empirically and analytically.

Possible Progress Steps

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

Download the directory lines to your system. It contains a number of sample input files, an implementation of quicksort, and reference solutions. If you're using arizona, you can directly access the files via the path ~cs226/ftp/lines/ and avoid using up your quota.

Reacquaint yourself with turtle graphics. The files point.h, point.c, and plotpoints.c form a program that reads in a list of points and plots the results using turtle graphics. Run plotpoints with some input, view the result using turtle and a Postscript viewer.

Before writing code, think carefully about the data structures and operations that you will need to support. For debugging, consider using a POINTshow() routine that prints a point in a more human readable form rather than POINTdraw().

Here are two nice observations that can greatly simplify your coding.

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 quadrant 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.
You can avoid using real numbers and trigonmetric functions. Observe that you don't actually need to compute the angles that two points, say q and r, make with p; what you really need is to be able to compare the angles that q and r make with p. You can do this by comparing (q.x - p.x) (r.y - p.y) with (r.x - p.x) (q.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. Not only do you speed up the computation by avoiding expensive arctangent function calls, but you also avoid issues with floating point precision.

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

COS 226 Home Page
nailon@cs.princeton.edu

Last modified: September 15, 2003