|
|
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.
How do I use gcc226 on arizona? The full path is /u/cs226/bin/gcc226. 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.
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 quicksort.c or any other code from the Sedgewick book or any code from lecture with an appropriate reference.
How do I measure the running time of my program in seconds from Unix, Linux or OS X? Use the command:
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./usr/bin/time a.out < 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 C code (don't forget to remove it before submitting) as in timing.c. Srivas Prasad '03 suggests chaing 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.
|
|
Input. Here are some sample input files. 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.
Compilation. Your two programs must be named brute.c and lines.c. By popular demand, we removed the requirement that you submit a file named item.c. However, this is not a license to practice bad modular design! A reasonable strategy would be to create and submit four files: brute.c, lines.c, point.c, and point.h. To compile each executable, we'll compile all the files you submit jointly (minus brute.c or lines.c). This should give you maximum design flexibility, while forcing both executables to share a common item.c or point.c file. Be sure to submit every file that your program needs. Don't forget to hit the "Run Script" button on the submission system to test that it compiles cleanly.
Reference solutions. For reference, we provide our executable code on Windows, Solaris, and OS X.
|
|
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:
|
|
These are purely suggestions for how you might make progress. You do not have to follow these steps.
|
|
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).