This homework is about implementing the Closest Pair O(n log n) algorithm in
Section 5.4 of the book, and comparing it with the straightforward
quadratic algorithm that I've already implemented here
. Your program should ask for the number of points to run on,
then generate this number of points (I've already done this), run
the quadratic algorithm and report the solution it finds and the time taken
(I've done this as well), and then run the O(n log n) algorithm, the
solution it finds and the time taken.
You have to submit the file containing the program source to a dropbox
called Homework4 that I will create on icon. In addition, you should
also submit a text file tabulating the time taken by the two algorithms
on inputs of size 500, 1000, 5000, 10000, 50000, 100000. For each
of the above sizes run the program at least 5 times and report the time taken
that in your judgement is typical.
If you're using a language other than Java for the homework (which is
okay), you'll have to re-do the parts that I have already done.