Description

For this assignment, you will write a multi-process program that takes advantage of multiple CPU cores in parallel to solve the Closest Pair of Points Problem. Background The closest pair of points problem is a computational geometry problem that can be solved using a divide and conquer algorithm. As a reminder of what a divide-and-conquer algorithm is: A divide-and-conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

A high-level explanation of the problem is explained in this handout. A more detailed explanation, which is required reading, is available in this PDF printout of Section 33.4 from "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein (CLRS). If you have any questions about the algorithm, to avoid clutter and to make the Piazza threads more useful for everyone, please avoid vague questions such as, "I don't understand Step X". Instead, please reference specific elements from the text in the handout or provided PDF file and ask a specific question about that text.

Instruction Files