Week 8

• Readability Score: 4 / 10
• Interest Score: 7 / 10

Section 5.3 Summary

Problem: Given n points on an X,Y coordinate plane, find the two points that are the smallest distance away from each other than to any other two points.

The initial solution to this problem is obvious:

This algorithm, however, is inefficient because it is . An optimization can be found with a divide and conquer algorithm in which we divide the plane in half and recursively find the closest pair of points. In this algorithm, a problem with boundary cases of points near the dividing line quickly arises but is squelched when we realize that points beyond a distance of half of the smallest distance so far don't have to be examined.

Problem: Given an n-digit number A and an n-digit number B, find the product A x B.

The initial solution to this problem is obvious:

Naturally, this algorithm is inefficient because its nested for loop makes it . By using a divide and conquer algorithm, we can divide up the problem and remove unnecessary operations to discover an algorithm that is .