Home -> Programming -> Planning -> Algorithmic Thinking

Algorithmic Thinking

  1. Enter the House
  2. Find the Correct Key
  3. Turn the Key
  4. The Complete Algorithm
  5. Patterns

When it comes to working out what actions should occur in any given event, we need to think in a particular way. In programming we call this Algorithmic Thinking. There are a finite set of thinking patterns which are sufficient for constructing algorithms. But there is an almost infinite number of ways to combine these patterns to produce different algorithms. The basic patterns are these:

That's it! All algorithms in structured programming are made up of this set and only this set of patterns. This was first established in the computer programming literature in 1966 although the ideas runs back to 1946.(1) There are, of course, some refinements in the implementation and use of these patterns, but there are no more patterns. The specific actions you can perform are determined by the programming language you are using, although all languages have a common core of actions that are available. Few people know them all and you will learn more as long as you are using VB. When we need to write a chunk of code for a program, we need to create a set of steps using these patterns. As an example of the process of using these patterns let's discuss the algorithm for entering a house.

Enter the House

Entering a house can be done in as few as one action, but can require several decisions and several actions. For our purposes we will assume that we have a set of keys, and know which house we are to enter and nothing more. At this point I will refer you to the definition of an Algorithm. The definition states that an algorithm is a set of steps, so the way to writing an algorithm is to format it as a numbered list. To create a step by step solution to a problem we must first know what the resolution of the problem is. If we do not know what the condition for solution is, we will not know when we have finished the solution. We must figure out the final outcome before we can do anything else. In this case the final solution is clear. We walk into the house. The next thing that needs to be done is to establish the starting point of the algorithm. For our purposes we shall use the description: Approach the the door. The algorithm at this point looks like this:

Enter House Algorithm
  1. Approach the door.
  2. Enter the house.

Note that the number of list items shown is random and does not indicate any knowledge of the number of steps we will need. Under some circumstances, this may be all that is required to reach a solution. However, for this example there are a few more steps. The next step in the process of creating an algorithm is to ask the question: What prevents me from performing this last step right now? There should be at least two obvious things which occur to anyone who has ever had to enter a house. These are:

We can add these two steps to our algorithm, but there is one consideration before we do so. That consideration is the order of these two steps. Again as anyone who has done this knows, we must unlock a door before we can open it. Our algorithm now looks something like this.

Enter House Algorithm
  1. Approach the the door.
  2. Unlock the door.
  3. Open the door.
  4. Enter the house.

We start with the first step and follow the algorithm step by step until we reach the last step. At no point is there a guarantee that we have not overlooked something, but when we start executing the algorithm, any such lack of necessary steps will become glaringly obvious. If we examine the list as it presently appears, there is one step that still requires some preparation. That step is Unlock the door. If we ask our question which tests for necessary prerequisite steps: What prevents me from unlocking the door? we conclude that we have to first find the correct key. Let's add that step to our algorithm. We will insert it after step 1, and before step 2 - which is where that step fits. Our algorithm now reads:

Enter House Algorithm
  1. approach the door.
  2. find the key which unlocks the door
  3. unlock the door.
  4. open the door.
  5. enter the house.

At first, this set of instructions would seem to be sufficient for our purposes. However, consider item 2 - how do you: find the key which opens the door? As we think about this question we soon realize that this description itself actually hides another set of steps which must be fleshed out for the algorithm to be understood and completely described. What at first appears to be a single action is actually a series of simpler actions. This is an example of insufficiency. Our algorithm is good but not sufficiently precise for it to be complete and absolutely clear. Algorithms for computer programs must be both! Now this can happen accidentally if we underestimate the precision needed for our actions. However, it is sometimes done deliberately when we know we have to break a step down into a simpler set of actions, but at the time we are not sure how to do it. This is called Black Boxing a problem!

Find the Correct Key

We start this process just like we did before. What is the outcome we want to achieve? Find the key which will unlock the door? We might ask how do we know it will do this. The straightforward answer is to have the door unlocked. This occurs when the key turns the cylinder. So this is the solution criteria for step 3 of the previous list. Now, what is the necessary input? We have to have a key in hand to start the process. In this case our process will look similar to the following:

Find Key Algorithm
  1. Select first key
  2. The key turns the lock unlocking the door

Now we start at the end and again ask the question: What prevents me from turning the lock in the door.? One obvious cause if the key doesn't fit in the lock. Finding a key which fits in the lock is a prerequisite to unlocking the lock. In plain terms then we are going to try each key in turn (which thinking pattern?) until we find a key that fits the lock, then we will try to turn the key. We will do this until we find a key which turns in the lock. (which thinking pattern?) What we have just described can be set up as one loop or two loops one nested inside of the other. We will do one loop since that is the simpler construct. It should look something like this: (Did you have the same idea?)

Find Key Algorithm
  1. Select first key
  2. repeat
  3.      try to insert the key into the lock
  4.      try to turn the key in the lock
  5. until key inserts into the lock and key turns in the lock

Now what is missing from our algorithm? Which key are we trying to fit and then turn? Does it ever change? The above set of steps is an actually an infinite loop since according to the way we have written this algorithm, we try the same key forever, so the loop will execute forever. Infinite loops are one of the main hazards in using loops. We must make sure our loops do not run forever! At some point we must add the instruction select the next key. If we think about how we do this physically, there are two separate causes of having to select the next key. First if the key will not fit in the lock, we go to the next key. Second if the key will not turn we go to the next key. Notice the use of the word if! This means I am making a decision, and the fact that I have two separate causes for which I need to change keys means that it must go in 2 places. Before reading further see if you can figure out where to place these changes from the code steps above this paragraph.

Find Key Algorithm
  1. Select first key
  2. repeat
  3.      try to insert the key into the lock
  4.      if the key will not insert then
  5.           select next key
  6.      try to turn the key in the lock
  7.      if the key will not turn then
  8.           select next key
  9. until key inserts into the lock and key turns in the lock

Did you get it right? Now we have a routine which will find the key - right? - always?? Notice we are still working with an assumption here. The assumption is that the correct key is one of keys we were give. Has that ever been untrue in your life? We cannot afford to leave assumptions unexposed in programming. They will make fools of us if we do! Now we do have two places in the routine where we are selecting the next key. this might be a bad thing, but if we think carefully about it, the cases are mutually exclusive. We first reject a key if it will not insert and once inserted we only reject a key if it will not turn in the lock. Following this procedure there is no chance of passing over the correct key. Right?

Notice we select the first key before we start our loops. As described above, we then run one loop to find a key which fits the lock. This must be the inner loop because this must happen before we find a key which turns in the lock. The second loop is to find which key turns in the lock to open the door. It is the outer loop because it happens last.

With a set of keys which we have not used before, we do not know which key unlocks the door. Therefore we go through the repetitive process of trying each key until we find the one which unlocks the door. The indentation is used to make clear that certain steps are subordinate to the enclosing structure. These steps are the ones that are being repeated - the heart of the loop. Now we are ready to integrate the two lists so we can get a complete set of instructions:

Enter House Algorithm
  1. Approach the the door.
  2. Select first key
  3. repeat
  4.      try to insert the key into the lock
  5.      if the key will not insert then
  6.           select next key
  7.      try to turn the key in the lock
  8.      if the key will not turn then
  9.           select next key
  10. until key inserts into the lock and key turns in the lock
  11. Open the door.
  12. Enter the house.

Turn the Key

This looks really good. If we want to be picky, and we must be picky when programming, there is one problem that still remains. Which way does a person turn the key? Of course the answer to this depends on whether the hinges are on the left side of the door or the right side of the door. Alternatively, is the lock closest to the left jamb or the right jamb. To make this distinction we see one of the first refinements of the decision thinking tool. So far we have only used a plain conditional tool which does something if a particular test is true, but does nothing otherwise. If we write this code with what we have learned to this point it will look like this:

Key Turning Algorithm
  1. if the doorframe is to your right then
  2.      turn the key 360 degrees counter-clockwise
  3. if the doorframe is on your left then
  4.      turn the key 360 degrees clockwise

The second decision tool is called a Forced Choice decision tool. It is used when we have two and only two possible outcomes (lock near left jamb or lock near right jamb), and the two outcomes are mutually exclusive. These choices are mutually exclusive because the lock is always on one side or the other. (Note there is a door lock system which mounts its locks in the center of the door - we will ignore this system for this example.) Altering the steps above to make use of this new thinking tool will make the steps look like this:

Key Turning Algorithm
  1. if the doorframe is to your right then
  2.      turn the key 360 degrees counter-clockwise
  3. else
  4.      turn the key 360 degrees clockwise
  5. end if

The Complete Algorithm

Now we will add this to our algorithm which gives us the complete and detailed set of steps that anyone should be able follow to enter a house.

Enter House Algorithm
  1. Approach the the door.
  2. Select first key
  3. repeat
  4.      try to insert the key into the lock
  5.      if the key will not insert then
  6.           select next key
  7.      try to turn the key in the lock
  8.      if the key will not turn then
  9.           select next key
  10. until key inserts into the lock and key turns in the lock
  11. if the doorframe is to your right then
  12.      turn the key 360 degrees counter-clockwise
  13. else
  14.      turn the key 360 degrees clockwise
  15. end if
  16. Open the door
  17. Enter the house

You can now see that for even a simple task, we have had to use all the Thinking Patterns introduced above. Lets review the four thinking patterns introduced above and used to create this algorithm. There are 17 lines of instructions representing 17 possible actions. Some of these actions are sequence sensitive. We cannot enter the house until we open the door. We cannot open the door until we unlock the door. We cannot unlock the door until we find the key which fits the lock. Even after we figure out all the tasks for an algorithm, we still must order them in the proper sequence. This is relatively easy for tasks which we understand, but for tasks we do not understand it becomes almost impossible. This is one of the most important reasons why we must write down the actions for each event we are trying to program. After we become familiar with standard sets of instructions we will not need to write things sown, but when we are learning to program, we make our task much much harder if we try to skip writing things out!

Notice there are two decisions which need to be made. Each decision consists of a comparison called a test in programming. In each case, if the result of the test is True, then we complete the action which is nested below the decision. Decisions provide us with the ability to direct how our program operates. For the second decision you should recognize that they are related. Since all doors which do not have the frame to the immediate right of the lock, must have their from to the immediate left of the lock, this is actually only one decision with two possible results as discussed above. You will be formally introduced to this variant and the others below.

The last pattern is repetition. We use this pattern all the time in life, but after a while we don't even recognize that we are using repetition. Without this pattern even simple tasks like counting to one million are almost impossible to program. Repetition is an indispensable tool in our toolbox of algorithmic thinking.

Another thing that should notice is that even apparently simple tasks actually break down into a fairly complex list of actions. One of the main reasons for this is that computers are incapable of making assumptions. The situation analyzed above contains several implicit assumptions. People make judgments about whether a door will be locked based on several things. Things like time of day places, whether a car is in the driveway, whether the dog is barking and so forth. Most of this we do without conscious thought based on our previous experience. Computers do not have previous experience - at least not so far. So we have to exhaustively anticipate and resolve every possible situation which we want our program to deal with. High quality software is very detailed and the attention to detail is a big part of what makes it so good.

We seem to have a fairly complete list of necessary steps. Now we can address some things which are a little weak in or proposed algorithm. If the door is open the action we need to take is enter the house. Notice the disclaimer 'if the door is open'. This indicates that at a minimum we would need to check the door to see it it was open - in other words make a decision. Anytime we would use the word if it indicates that a decision is involved. The best way to get started is to write a brief description of what has to happen. It is usually best to do this in point or list form.

The Thinking Patterns

Sequence the Actions in the Correct Order

All programming languages are made up of statements, actions which can be performed, and grammar, the structure of the language. To do anything in a programming language we must learn the basic statements of the language. Secondly we must put those statements in the correct order.This is the sequence aspect. As in the example above, we cannot open a door until it is unlocked. While this idea is simple in principle, in practice it is a lot more difficult to determine the order a set of statements should follow to get the result we desire.

Decision Patterns

There are four standard decision structures which correspond to VB language structures which you will learn of later. By learning to think of decision in these four standard patterns, it becomes easier to create your code. The four patterns are:

  1. Conditional - A comparison is performed. If the test is True an action or set of actions are performed. No action is performed if the Test result is False.
  2. Forced Choice - A comparison is performed. If the test is True actions A are performed, while if the test is False actions B are performed.
  3. Multi-option one decision - A variable is examined. Based on the value of the variable one of several actions is performed. This option can also have an action/set of actions which are performed if no matching conditions are found.
  4. Multi-option many decisions - Several comparisons are performed and different actions are performed based on the results. This option can also have an action/set of actions which are performed if none of the comparison are True.

Each of these decision tools are used in standard ways which you will learn as you go through these tutorials.

Loop Patterns

There are two standard ways in which loops can be set up. Loops are used to repeat a set of instructions. By looping we forego having to retype each subsequent repetition and we obtain improved reliability with fewer lines of code. The two loop patterns are:

  1. Pre-test Loop - This pattern is used when we want to have the possibility of never executing the loop.
  2. Post-test Loop - This pattern is used when we know that the loop must be executed at least once.

(1) Structured Programming theorem by Corrado Böhm & Giuseppe Jacopini

reference here