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.