1.3 Algorithms

Algorithms are step-by-step methods of solving problems. The process of reading in names previously described is an example of an algorithm, though a very simple one. Some are extremely complicated, and many vary their execution depending on input. Often algorithms take input and generate output, but not always. However, all algorithms have something in common: they all do something.

Imagine a website like Google Maps, which has an algorithm to get directions from one point to another in either North America or Europe. It typically requires two inputs: a source and a destination. It also gives two outputs: the narrative directions to get from the source to the destination, and a map of the route.

The directions produced are also an algorithm; they accomplish the task of getting from the source to the destination. Imagine getting the directions to your friend’s house shown on the map in Figure 1-1.

Figure 1-1. Directions “algorithm”

First notice that the directions are numbered; each step happens in sequential order. Additionally, it describes general steps like, “Turn left (east) on Main Street.” It does not say, “Turn on your left turn signal and wait for the light to turn green, and then turn left on Main Street.” That is not the point of an algorithm. An algorithm does not need to write out every single detail, but it needs to have all the important parts.

1.3.1 Algorithm Efficiency

Different algorithms may accomplish the same task, but some will do it much faster than others. Consider the algorithm just described for going to your friend’s house, which certainly is not the only route to her or his home. Instead of getting on Ruby Lane, you could have hopped on the expressway, gone to the airport, and then taken a cab from the airport to your friend’s house—but that would be extremely inefficient. Likewise, there may be a more efficient route to your friend’s house than the one described. Just because you have created an algorithm does not make it efficient, and being able to create efficient algorithms is one of the factors that distinguishes a good computer scientist. For example, imagine receiving the following set of directions to your friend’s house instead of the ones shown in the previous section, illustrated on the map in Figure 1-2:

1. Start going south on River Road.

2. Turn left (east) one block south of Main Street onto Algorithm Circle.

3. Continue until you come to 345 Algorithm Circle (your friend’s house).

Figure 1-2. Directions “efficient algorithm”

Here we use a different algorithm that accomplishes the same task, and it does so slightly more efficiently. That is, fewer turns are involved.