Outer Limits of Reason (22 page)

How much work was done? To obtain the minimum of all the elements we need to look at all
n
elements. To find the minimum of all the elements except the first one we need to look at
n
-
1 elements. Continuing in this way, we see that to perform the entire selection-sort algorithm, one must look at

n
+ (
n
− 1) + (
n
− 2) +
^. . .
+ 2

elements. It turns out that this sum is about half of
n
²
and so we will say that the selection-sort algorithm requires at most
n
²
operations.

Other, more sophisticated sorts demand fewer operations. One such algorithm is called the
merge-sort algorithm
. We need not get into how the merge-sort algorithm works. Suffice it to say that for an input of size
n
, this sort algorithm demands

n
× log
₂
n

operations. For example, given an unordered list of size 1,000, the merge-sort algorithm would sort the list with

1,000 × (log
₂
1,000) = 1,000 × 10 = 10,000

operations.

You might think that there is not much of a difference between
n
²
and
n
×
log
₂
n.
Perhaps it is not worth the effort to have this fancier algorithm. Well, it is! Consider the task of sorting the four million numbers of the Brooklyn telephone book.
²
An
n
²
algorithm that sorts the four million entries will have to perform 16,000,000,000,000 operations. In contrast, if the more efficient
n
× log
₂
n
algorithm is used to sort the four million entries, approximately 88,000,000 operations would be required. This is a vast improvement.

Euler Cycle

Königsberg is a city in Russia that used to be part of Prussia. The city is on both sides of the Pregel River, and Kneiphof Island is in the middle of the river.
³
The main parts of the city and the island were connected by seven bridges, as in
figure 5.4
.

Residents used to wonder if it was possible to take a leisurely stroll through the city in such a way that one starts and finishes in the same place and crosses each of the seven bridges exactly once. Try to find such a path.

In 1736, the question was posed to Leonhard Euler (1707–1783), one of the greatest mathematicians of all time. He realized that to find such a path through the seven bridges we do not care if the pedestrian stops for ice cream, wanders about, has a barbeque, or completes the trip in three days. What does matter is the way the land and the bridges are connected. He noticed that you might as well think of each landmass as a single point. It also does not matter how wide the bridges are or how old they are or how far away they are from each other. The only relevant information is which land masses the bridges connect. One might as well think of each bridge as a single line connecting the points. We can envision these points and edges superimposed on the map of Königsberg, as in
figure 5.5
.

With this insight, Euler essentially started the field of mathematics known as
graph theory
. A graph is a collection of vertices (or points) and edges (or lines) between the vertices.

A graph describes a relationship between things. Since “things” is general, graph theory has many diverse applications and has become one of the most important branches of mathematics. For example, graph theory can describe computer networks: the vertices would correspond to computers and an edge between two vertices would correspond to the connection between them. Another example is the World Wide Web: the vertices of a graph can represent web pages and an edge represents a link from one web page to another. A subway map is another common example of a graph.

Here is an interesting application of graph theory. Consider the graph whose vertices correspond to every person on earth today. Let there be an edge between any two people who are acquainted with each other. Researchers believe that in this graph, the maximum number of edges that one needs to traverse in order to connect any two vertices is six. That means that given any two people, there is a sequence of the first person who knows someone who knows someone who . . . who knows the second person. The sequence, in general, does not need to be longer than six. This is known as the “six degrees of separation.”

Let us return to the Königsberg Bridge Problem. Once Euler ignored the unimportant part of the problem, he was easily able to see that no such path was possible. Euler reasoned that every time strollers enter a landmass or a vertex, they must also be able to leave the vertex. Of course, the strollers might come to that vertex again, but then they must leave again. Euler realized that a requirement for there to be a path is that every vertex must have an even number of edges touching it. If this requirement is met, then there is a path that starts and finishes at the same place and passes every edge exactly once. If this requirement is not met, then no such path exists. Since every vertex in
figure 5.5
has an odd number of edges/bridges touching it, no such cycle is possible.

One need not be concerned with strollers in old Prussian cities to be interested in this problem. Given any graph, we call a path that starts and finishes at the same vertex a cycle. A cycle that passes every edge exactly once is called an Euler cycle. So for any given graph, we may ask if there exists an Euler cycle. This is the
Euler Cycle Problem
. We saw that the graph in
figure 5.6
does not contain such a cycle.

Notice every vertex has an odd number of edges touching it. In contrast, consider the graph in
figure 5.7
.

Every vertex touches an even number of edges and hence there does exist an Euler cycle. (Try to find one!)

We may drop the requirement that the paths start and end at the same vertex and pose the
Euler Path Problem
: Given a graph, does a path exist that crosses every edge exactly once but need not start and finish at the same vertex? With an understanding of Euler's requirement for an Euler cycle, the answer to the Euler path problem is obvious: there is such an Euler path
if at most two
vertices have an odd number of edges touching them and the rest of the vertices have an even number of edges touching them. The two vertices will be the starting and ending points of the desired path. Consider the graph in
figure 5.8
.

There is an Euler path from the top vertex to the bottom and vice versa, but no Euler cycle.

What does this have to do with computers and algorithms? Without the information presented in the previous few paragraphs, we might have thought that to determine whether a graph has an Euler cycle we would have to try all possible cycles and see if any cycle crosses every edge exactly once. For a large graph there is a tremendous number of cycles to check. Now, with Euler's trick in hand, we have a new method of determining if there is an Euler cycle. This trick has us simply verifying that every vertex has an even number of edges touching it, which can be done with relatively few operations. Euler's method has saved us a lot of work. We will always be looking for such tricks.

All problems presented in this section can be solved with algorithms that demand a polynomial number of operations such as
n, n
²
,
or
n ×
log
₂
n
operations. Such problems are called
polynomial problems
. The collection of all polynomial problems is denoted as
P
. Most polynomial problems can be solved on a modern computer in a feasible or tractable number of operations. Such problems take a feasible amount of time to solve.

In contrast to the feasible problems discussed here, in the next section, we will look at infeasible or intractable problems—that is, problems that are unsolvable in a reasonable amount of time.

5.2  Some Hard Problems

To get a feel for how hard some problems are, let us introduce the following five problems, which are easy to describe.

The Traveling Salesman Problem

Consider a salesman who wants to drive to six specific cities across the United States. He would like to visit each city exactly once and when he is done with all of them, return to the starting city. There are many different routes that he can take. Our parsimonious traveler would like to travel the shortest route in order to save time and money. He looks up the distances between these cities and finds the information in
table 5.2
.