Tom’s favorite activity is putting together 1,000-piece puzzles (odd, but uniquely shaped cardboard pieces that are die-cut from a single complete scene). Using shape and coloration as cues, Tom picks...

Tom’s favorite activity is putting together 1,000-piece puzzles (odd, but uniquely shaped cardboard pieces that are die-cut from a single complete scene). Using shape and coloration as cues, Tom picks up two pieces and tries to fit them together, possibly rotating one or the other. Sometimes Tom misjudges, and the two pieces don’t fit together properly; he then has to put the two pieces back on the board and try again. When they do fit together, Tom places them on the board, where they are then considered to be a single piece. Tom then repeats the process. Since developing an interest in computer science in general, and parallel programming in particular, Tom has rigged up a video camera over a small table on which he has spread all pieces of the current puzzle on which he is working. This camera is linked to one of his N computers (yes, he has N home computers, ranging from a now ancient 2 GHz P4 to a 64-CPU P9 with its 256-bit data path and a 12 GHz clock) producing a compact 30,000 × 30,000 pixel image. Tom’s goal is to have the N computers working in parallel to produce a list of directions for assembling this puzzle in the fewest steps. (Easy) List all of the aspects of computer science that need to be brought together in order for Tom to solve this parallel computing problem; explain the role each plays. (Harder) Outline an approach Tom could use to solve this puzzle problem on his N computers. Identify the steps he needs to take, but do not actually carry out the programming that would produce the puzzle-assembly directions. (Still harder) Outline what would need to be done if the shapes of the pieces were not unique. (Difficult) Implement such a puzzle-solver on whatever parallel system you have available.