The Algorithm Design Manual
Many important problems can be reduced to sorting, so we can use our clever O(nlogn) algorithms to do work that might otherwise seem to require a quadratic algorithm.
An important algorithm design technique is to use sorting as a basic building block, because many other problems become easy once a set of items is sorted.
It is a rare application where the running timeof sorting proves to be the bottleneck, especially a bottleneck that could have otherwise been removed using more clever algorithmics. Never be afraid to spend time sorting, provided you use an efficient sorting routine.
Sorting lies at the heart of many algorithms. Sorting the data is one of the first things any algorithm designer should try in the quest for efficiency.
Sometimes it is required to leave the items in the same relative order as in the original permutation. Sorting algorithms that automatically enforce this requirement are called stable. Unfortunately few fast algorithms are stable. Stability can be achieved for any sorting algorithm by adding the initial position as a secondary key.
A spanning tree of a graph G = (V, E) is a subset of edges from E forming a tree connecting all vertices of V. For edge-weighted graphs, we are particularly interested in the minimum spanning treethe spanning tree whose sum of edge weights is as small as possible.
Minimum spanning trees are the answer whenever we need to connect a set of points (representing cities, homes, junctions, or other locations) by the smallest amount of roadway, wire, or pipe.
A minimum spanning tree minimizes the total length over all possible spanning trees. However, there can be more than one minimum spanning tree in a graph.
Lossy versus lossless encoding is the primary issue in data compression.
A triangulation in the plane is constructed by adding nonintersecting chords between the vertices until no more such chords can be added.
The simplest such O(n lg n) algorithm first sorts the points by x-coordinate. It then inserts them from left to right as per the convex-hull algorithm of page 105, building the triangulation by adding a chord to each point newly cut off from the hull.
Does the shape of the triangles in your triangulation matter? - There are usually many different ways to partition your input into triangles. Consider a set of n points in convex position in the plane. The simplest way to triangulate them would be to add to the convex-hull diagonals from the first point to all of the others. However, this has the tendency to create skinny triangles.