Find two closest points in a set of n points in a two-dimensional Cartesian plane.

Brute Force Solution:

• Compute distance between every pair of distinct points and return indices of the of points with the smallest distance.

Q: What is the basic operation?

A: Calculating the distance between two points.

e.g., suppose you want to find the distance between Point A and Point B.

P_{AB} = \sqrt{ (x_a - x_b)^2 (y_a - y_b)^2 }

The basic operation is sqrt.

Q: How many times does basic operation execute?

A:

We know it depends on the # of different pairs of points.

More formally:

We can use the product rule (CS1300) to get:

C(n) = \frac{n \times (n-1)}{2}

We divide by two to avoid double-counting of A \leftrightarrow B and B \leftrightarrow A

Thus, this algorithm is in O(n^2)

Strengths and Weaknesses of Brute Force

Strengths

• Widely applicable
• Simple

Weaknesses

• Rarely efficient
• Not as constructive as some other design techniques.

Exhaustive Search

A brute force solutoin to a problem involving search for an element with a special property, usually among combinatorial objects such as permutations, combinations, or subsets of a set.

TODO Method

On Performance: Exactness is Costly

• Runs in realistic time only on very small instances.
• In some cases, there are better alternatives.
• In many cases, exhaustive search or a variation is the only known way to get an exact solution.

Example: Traveling Salesman

Given n cities with known distances between each pair, find the shortest tour that passes through all the cities exactly once before returning to the starting city.

TODO Example

There are (n-1)! ways to traverse this.

• (4*3*2*1)

Example: Knapsack Problem

Find most valuable subset of items that fit into the knapsack.

Example: Assignment Problem

The exhaustive solution is a n! solution!