The algorithmic solutions developed by programmers and problem solvers can take on a virtually infinite number of diverse forms. They can be brief, requiring only a few operations to implement or they can be massive and complex, spanning millions of lines of code and a team of programmers to keep it all straight. But despite this range of diversity, all of these algorithms are characterized by the same basic elements of sequencing, selection, and iteration.
A good problem solver can learn to recognize these three features and easily use them to construct simple, effective, and elegant solutions to the problems they might want/need to solve.
With repeated practice throughout this course, you’ll develop a trained eye that can quickly recognize each of these common patterns within your everyday actions. In fact, if you stop to take a closer look at a few of the common, everyday tasks that you perform all the time, you’ll likely discover that you already make use of these patterns without even noticing.
In the next few units, we’ll see that all programming languages are designed to make it easy for programmers to write code that uses these three basic patterns.
The simplest of all of the patterns consists of each step of an algorithm following the previous step. When the steps of an algorithm are sequentially arranged, each instruction is executed one at a time in the order specified by the algorithm.
1) put on pants 2) put on left shoe 3) put on right shoe 4) put on shirt
One of the most important things to recognize about the sequencing of instructions is that it enables one to explicity state the order in which certain instructions are executed. Depending on the situation, sometimes an instruction needs to precede one or more other instructions in the same algorithm. This is often the case if a “later” step is dependent upon the successful completion of an “earlier” step.
In the above example,
put on pants is sequenced to come before
put on left shoe and
put on right shoe which makes sense, since it would be difficult to put on pants after putting on shoes.
However, just because sequencing imposes an order on which instructions are executed doesn’t mean that order is important or even necessary.
Again, in the previous example, the order of
put on left shoe versus
put on right shoe probably doesn’t matter. That is, the algorithm could probably work just as well with the right shoe preceding the left shoe. Similarly,
put on shirt, which is currently the last step, could probably have been placed anywhere in the algorithm, either before or after the pants and shoes, without affecting its correctness.
Algorithms that consist only of sequencing will always perform exactly the same, regardless of external conditions, which is often good for designing specific solutions to specific problems.
However, most problems would benefit from a more generalized solution that can dynamically adapt to changes in conditions. More specifically, problems that handle variable data, such as user-supplied input, oftentimes need to execute different sequences of instructions depending on the particular conditions.
In these “conditional” situations, algorithms need a way to select which sequence of instructions should be executed and which should not.
The classic metaphor used for this type of situation is an “if... else...” sort of structure. Literally (since most languages actually use the keyword
if), the algorithm asks a question (specifically a “YES/NO” question) and the answer to that question is used to determine which path of the algorithm to execute and which path of the algorithm to skip.
1) if wearing pants... 2) ...put on left shoe 3) ...put on right shoe 4) else... 5) ...put on pants
In the above example, the
if condition at Step 1 creates a fork in the algorithm that enables one of two possible sequences of instructions to be executed. If the condition
wearing pants is true (i.e., the pants have already been put on at some earlier time in the algorithm), then it’s safe to put on one’s shoes. In that case, Steps 2 and 3 (
put on left shoe and
put on right shoe) will be executed while Step 5 (
put on pants) will be skipped. However, if the condition was false (i.e., not wearing pants), then someone better put on some pants! In that case only Step 5 will be executed while Steps 2 and 3 will be skipped.
It’s important to note that the nature of an
if/else question, or condition, always allows for only two possible answers (e.g., yes/no, true/false, etc.) because each answer is used to select one of the two specified sequences – the first sequence/branch if, and only if, the condition is true or, alternatively, the second sequence/branch if, and only if, the condition if false.
If more than two branches are ever needed, they can be achieved by “nesting” multiple if/else clauses together. That is, one or both of the two branches can contain its own internal if/else clause. For example:
1) if wearing pants... 2) ...if wearing shoes 3) ...put on shirt 4) ...else... 5) ...put on left shoe 6) ...put on right shoe 7) else... 8) ...put on pants
This example tests for and handles three different situations:
- If you’re already wearing pants and shoes... put on your shirt.
- If you’re already wearing pants, but no shoes... put on your shoes.
- If you’re already not wearing pants... put some pants on ASAP!
Note that in the first and second situations, Step 8 will be ignored completely because of the pants-wearing status. Then, depending on the shoes-wearing status, either Step 3 will be executed or Steps 5 and 6 will be executed. Likewise, in the third situation (no pants!), the condition about shoes is irrelevant as Step 2 (and its subsequent Steps 3-6) will be ignored.
The third common pattern that you’ll see in most algorithms, especially with large and complex solutions, is repetition – more properly referred to as iteration.
For example, consider the very simple act of hammering a nail into a block of wood:
1) grab a hammer 2) raise the hammer over your head 3) aim for the head of the nail 4) swing hammer down onto the head of the nail 5) raise the hammer over your head 6) aim for the head of the nail 7) swing hammer down onto the head of the nail 8) raise the hammer over your head 9) aim for the head of the nail 10) swing hammer down onto the head of the nail 11) ... N-1) N) put down the hammer
When you look at it this way, the repetition becomes immediately obvious. Steps 2–4 are repeated again as Steps 5–7 and Steps 8–10, etc. Each of these repeated sections of steps is called an iteration. If we were to continue this algorithm, what do you think Steps 11–13 will be? What about Steps 14–16? 17–19? How many iterations will we need? When will these instructions stop? When should they stop?
And more importantly, if we ever needed to actually write out these detailed instructions for someone else, like maybe a robot, to follow, even a simple task like hammering a nail might become extremely long and tedious to write. But we don’t normally think of tasks like this in such overwhelming ways. Instead, we simplify the tasks in our mind. That is, we apply abstraction (a topic we’ll cover in more detail throughout this course).
For example, in the real world, if you were actually driving a nail into a block of wood, you’d know to repeatedly swing that hammer over and over until you knew it was time to stop (i.e., when the nail head was flush with the wood surface).
Now think about that. You intuitively know to repeat a certain set of instructions ("Raise,” “Aim,” “Swing") until a certain condition is met ("Nail head is flush with the wood surface"). And that condition that helps you decide whether to repeat those “Raise-Aim-Swing” instructions one more time or to stop and put the hammer down is just like the condition we saw above in the section on selection.
This familiar pattern of repeating sections of instructions until a condition is met can be seen as a special case of selection in which one of the branches loops back to test the condition again.
Putting this into words, we might use a phrase like
Go back to Step #__ to indicate that the flow of a program should not continue sequentially to the next step, but should instead jump back to an earlier step.
1) if the problem still exists... 2) ...take action to solve it 3) ...go back to Step 1 4) the problem no longer exists
In the above example, whatever action is being performed in Step 2 will continue to be repeated over and over again until the problem is solved. Notice how Step 3 explicitly states that the algorithm should go back to Step 1 where the condition (i.e., “Does the problem still exist?”) can be tested again. The condition then determines whether another iteration is needed or if the loop can be exited and the program can continue on with whatever comes after this loop. That is, Step 4 is like an implicit “else” branch of an “if/else” clause. It will only be executed when the “if” condition in Step 1 is false.
The previous example is an example of an “indefinite loop”—a form of iteration in which the number of times that the loop will execute is not explicitly stated in the algorithm. In these types of problems, we can use a
repeat until notation to specify that the loop should continue indefinitely until a particular condition is reached.
1) repeat until... 2) ...
Our example of hammering a nail into a block of wood is an excellent example of an indefinite loop. The instructions are to essentially repeat the “Raise-Aim-Swing” action over and over until the nail is flush with the wood. The exact number of swings of the hammer that are needed are indefinite.
However, in many other types of problems, it is often necessary to repeat an action a specific number of times. In these cases, we can use explicitly state an exact number of iterations that we need a particular section of the algorithm to be executed using the
repeat N times notation, where
N is the number of iterations desired.
1) repeat N times... 2) ...
Finally, it’s important to note that most algorithms are not limited to only one of these three common flow patterns. In fact, most programs make use of a combination of these three patterns. Oftentimes, a number of selection blocks are arranged together in sequence. Or, as we saw earlier in the hammer/nail example, a sequential series of steps may make up the body of the loop (i.e., the instructions that keep getting repeated).