08.md

title
Closest-Pair Problem

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]{.underline} 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.

• ($432*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!