Garrett's Journal

• 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 .

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

This section of the reading describes mergesort as the most canonical divide-and-conquer algorithm. A divide-and-conquer algorithm is an algorithm that divides the input into multiple pieces (usually 2), solves each subproblem using recursion, and then combines the results of those recursive calls into a solution. As with all recursion, the recursive calls in a divide-and-conquer algorithm need to have a base case so that the algorithm has a point at which it stops dividing and starts conquering. Usually this “bottom out” point is when the recursive method is called on an input of some predefined constant size, such as 1.

Divide-and-conquer algorithms are a little less straightforward in computing an algorithm's time complexity, but their efficiency can be expressed as a recurrence relation. Mergesort can be measured by the number of comparisons based on the input size. This measurment can be expressed as a function that computes the number of comparisons (or “time”) based on the input size n:

A generalized form of the recurrence relation equation mentioned above is:

where q is the number of subproblems per step in the recursive algorithm. This gives us a few cases depending on what q is…

A good way to quantify the differences between two comparable sets of data is to determine the degrees of difference between the two. A generalized way to do this is to calculate the number of inversions between the two. Assuming the data in question is organized like two lists of the same set of elements, an inversion is the minimum number of times that two elements need to trade places in the first list to become the second list. For example, if you have the following list:

and you are comparing it to:

you could quantify the differences between them by saying that it would take 3 inversions to get from the first list of data to the second list of data:

We can use the algorithm on Pages 224-225 to count inversions. This algorithm has a time complexity of: , meaning that that is the the time it would take to find the number of inversions and perform them.