For the hardcopy you should submit the following itmes in the listed order. Ifyou submitted portions on the early date, attach that to the back of what you submit on the due date.

A signed cover sheet with your name legibly written on it.
Any code that you wrote or modified. Plese do NOT submit any provided code that you didn't modify. Also, if you modified a small portion of some provided code, just submit the portion you modified with th changes you made higlighted or clear makred in some way. Please try to print your code in two column format (landscape mode) to reduce paper usage.
If your implementation is buggy and you were unable to fix the bugts, please let us know what you think is wrong and give us output from some test case that shows the error. You'll lose fewer points for indicating there is a problem than you would if we discovered it ourselves.
For Part One you should provide a transcript showing the output for both the brute force and divide and conquery algorithms (the closest pair of points, the distance, and the running time in milliseconds) for inputs of size: 4, 10, 25 275, and 1000. Please combine all outputs in a single file. If the points you obtained from the random point generator do not match those on the web page, please use the provided data sets.
If you completed the Splitting Part of the Divide-and-Conquer algorithm (but not the rest) then insetad of doing the above, for n=10 output the points in both the left and right halves of the top-level recursive call sorted by x-coordinate and sorted by y-coordinate. You should check if your output is correct and if not indicate what it shoudl be. Once you have this working correctly, then you'll be ready to make the recursive calls and then combine. The idea of separting this part is so that you first debug the dividing part before going further.
For Part Two, you should submit a graph (easily created via Excel or the program of your choice) showing the running time in milliseconds of both the naive and divide-and-conquer algorithms as a function of the input size. (It is best if you use an average value computed over 100 runs). Your graph should label the axes, include a key, and so on. There is no need for you to submit the answers output -- just the graph is needed. Briefly indicate if your graph look as expected and if not, try to explain why. Also, tell us how large you were able to make n before the divide-and-conquer algorithm took over a minute.
Note: You can use whatever step size for increasing n that you feel is appropriate. Just be sure that you have included at least 10 different values of n for both the brute force and divide and conquer algorithm and that your largerst value of n is one for which the brute force algorithm ran at least a couple of minutes.
For Part Three, you should include a clear and concise description of the algorithm you implemented. If it is not obvious that your algorithm will always output the right answer convince us why it will. You can just replace the graph discussed above in Part 2, by a graph that has three plots (one for each algorithm). Briefly discuss how fast your algorithm was as compared with the brute force and divide-and-conquer algorithms and why you think this performance occured. If you did some additional experiments to answer this question, feel free to show those.

Return to the CSE 241 FAQ Page