Euclidean distance *d*(*P _{i}*,

Find the minimal distance between a pairs in a set of points

**Algorithm** BruteForceClosestPoints(*P*)

// *P* is list of points

*dmin* ←
∞

**for** *i* ← 1 **to** *n*-1 **do**

**for** *j *← *i*+1 **to** *n*
**do**

*d* ← sqrt((*x _{i}*-

**if** *d* < *dmin*
**then**

*dmin* ←
*d*; *index*1 ← *i*; *index*2 ← *j*

**return** *index*1, *index*2

Note the algorithm does not have to calculate the square root

Then the basic operation is squaring

*C*(*n*) = ∑_{i}_{=1}^{n}^{-1} ∑_{j}_{=i+1}* ^{n}* 2 =
2∑

A set of points is convex if for any two points, *P* and *Q*, the entire line segment, *PQ*,
is in the set.

Illustrate convex and non-convex sets

Convex-hull of a set of points is the smallest convex polygon containing the set.

Illustrate the rubber-band interpretation of the convex hull

The convex-hull of a set of points is composed of some subset of points in the sets.

How to find this subset? Consider the rubber-band figure. What properties do the line segments share?

The rest of the points of set are all on one side.

Two points (*x*_{1},
*y*_{1}), (*x*_{2}, *y*_{2})
make the line *ax* + *by* = *c*

where *a* = *y*_{2}-*y*_{1}, *b* = *x*_{1}-*x*_{2}, and *c* = *x*_{1}*y*_{2} - *y*_{1}*x*_{2}

And divides the plane by *ax*
+ *by* - *c* < 0 and *ax* + *by* - *c
*> 0

So we need to only check *ax*
+ *by* - *c* for the rest of the points

What is the worst case cost of the algorithm? O(*n*^{3})

Exhaustive search requires searching all the possible solutions (typically combinatorial objects) for the best solution.

Exhaustive search is simply a brute-force approach to combinatorial problems. (Levitin)

The minimal path through all vertices of a weighted graph, visiting each vertex only once.

The Hamiltonian Circuit is a cycle that passes through all the vertices of the graph exactly once.

So they are the same for an un-weighted graph. How to transform a weighted graph?

We concentrate on the **Hamiltonian
Circuit**. If there does exist a circuit then any point can be the start and
end vertices. Once a start vertex is chosen then we only need the order of the
remaining *n*-1 vertices. We could
generate all the possible ordering of the vertices and calculate the length of
the path.

How many possible combination? (*n*-1)!

Cost for calculating the path? Θ(*n*)

So the total cost for finding the shortest path? Θ(*n*!)

Note that half the paths can be eliminated by the direction,
so Θ(*n*!/2)

Given a *n* item
with weights *w*_{1}, *w*_{2}, ..., *w _{n}* and values

We could generate all possible subsets of items, check feasibility and then value, choosing the sub-set with the maximal value.

How many subsets of n items? 2^{n}

Both of the problems are NP-hard, meaning there is no know algorithm that solves the problem in polynomial time.

Assign *n* workers
to *n* jobs. Each worker charges a
different rate for each job specified by the cost matrix *C*[*i*,*j*].

Note each worker must be assigned to one and only one job.

The cost matrix specifies the problem instance.

A solution can be specified by an n-tuple that specifies the job assignment for the first, second, etc worker.

Then an exhaustive search would generate all the permutations and search for the minimal cost.

Cost of this algorithm? Θ(*n*!)

There is a better algorithm called the *Hungarian method* developed by Kong and Egervary.