CIT 594 Assignment 10: ForkJoin
Spring 2012, David Matuszek

Purposes of this assignment

• Get you started with Java's ForkJoin.

General idea of the assignment

Randomly generate one million (x, y) points, where 0.0 <= x < 1.0 and 0.0 <= y 1.0, and x and y are of type double. Then find and print out the two closest points, along with the distance between them.

Do this as quickly as possible, and print out the time required in seconds, as a floating point number.

Use ForkJoin. If you have a dual-core or quad-core computer, this should make your program about 2x or 4x faster. If you don't, using ForkJoin will slow things down slightly--but use it anyway!

Detailed specification

Generating random points

Since I need to be able to check if you got the right answer, I need some control over the "random" points you generate. So I would like you to generate them exactly as follows:

1. Ask the user to input an integer.
2. Use the integer as the seed to your random number generator. That is, static Random rand = new Random(seed); Do this only once, at the beginning of the program.
3. Generate points as follows:
   1. The first random number is the x value of the first point.
   2. The second random number is the y value of the first point.
   3. The third random number is the x value of the second point.
   4. The fourth random number is the y value of the second point.
   5. The fifth random number is the x value of the third point.
   6. Etc.

Observations on efficiency

Nothing beats a good algorithm.

On my home computer (2.8 GHz quad core), using a sequential program to compare every point against every other point, I got the following numbers:

• 100,000 points took 142 seconds.
• 66,000 points took approximately 1 minute.

But obviously some pairs of points are so far apart that you don't even need to consider them. I used a simple trick to eliminate many of these pairs, and got the following timings:

• 100,000 points took approximately 0.2 seconds.
• 1,000,000 points took approximately 10 seconds.

Using ForkJoin gave me approximately another 4x speedup.

Testing

How do you know you have the correct answer?

Comparing every point against every other point is really simple, and you can probably write that without error. Test it for a small number of points, say, 1000. Then see if your fancier algorithm gives the same answer.

Due date

Your program is due before 6am Tuesday, April 17. Zip up the entire directory for this project, and submit via Blackboard. Only assignments submitted via Blackboard will be accepted--any assignments emailed to me will be discarded without comment. A late penalty of 5 points per day (out of 100 points) will apply.

Because many of you are interviewing this semester, a limited number of 48-hour extensions will be available. To get an extension, email me before 5pm Friday, stating the reason you need the extension. No extensions will be granted after Friday. If you get an extension and fail to get the project in by the extended due date, late points will be counted from the original due date.