Algorithms and Pseudocode

---

The hardest part of designing a program using a language, such as C#, is not trying to work out how to express a specific algorithm in C#. The hardest part is to construct the algorithm itself. Often, complex algorithms are the result of many years of research. The majority of those complex algorithms could be implemented by a proficient C# programmer in a few hours or days.

Expressing algorithms is often facilitated through a "language" called pseudocode. To illustrate what pseudocode is and how it can be a useful way to express algorithms, consider the following situation.

An alien, from planet Blipos, is visiting earth for a brief period of time. He needs to know how the average of an arbitrary list of numbers is calculated. This will allow him to perform a few very important calculations on his spaceship computer so he can take off again. The computer is to be programmed in his favorite language, C#.

His mind, being between a man's and a machine's, is a bit peculiar. He understands English but will only understand instructions if they are exactly to the point. He is not able to make any assumptions. Phrases such as "Sum up the numbers and then divide by the amount of numbers in the list." are too vague. Determining the "amount of numbers in the list" would be one of his problems in this particular case. His big advantage, though, is the ease with which he converts precisely given instructions into C# source code.

How can we best explain to the alien the method of finding the average of any list of numbers? The following shows what we might tell him.

"Here are the steps to calculate the average of a list of numbers. Please start with step 1 and follow the steps in the sequence they are presented. You must remember to repeat the sequence: 3.a, 3.b, 3.c and 3.d for every number in the list, as stated in 3."

1. Take a piece of paper and a pencil.

2. Write two zero's on the paper, one on the left side and one on the right. Call the left zero Sum and the right zero ListSize.

3. Repeat the following sequence (3a-3d) for each number in the list:

   3.a. Add the number to the Sum on the paper.

   3.b. Replace the old Sum on the paper with the result of 3.a.

   3.c. Add 1 to the ListSize.

   3.d. Replace the old ListSize on the paper with the result of 3.c.

4. Divide the Sum by the ListSize and write this number down.

5. Read the number you wrote down in 4. It is the average.

6. End of calculation.

When the alien receives these instructions, he quickly tries out the algorithm on this simple list of numbers {1,2,3,4,5} because he knows by heart that the average of this particular list is 3. He grabs a piece of paper. Figure 2.1 shows what he wrote.

Figure 2.1. How the alien calculated the average of {1, 2, 3, 4, 5} .

To get a good first-hand understanding of what it "feels" like to be a computer executing an algorithm, pretend for a moment that you are the alien and choose a short list of numbers. Follow each step of the algorithm given to the alien blindly and find the average of the numbers.

The test performed by our alien doesn't prove the correctness of the algorithm, but it seems to satisfy the alien, who, with a big smile, runs back to the spaceship where it is easy for him to convert the algorithm into C# source code. It is then fed into the space shuttle computer.

Five minutes later, our alien happily leaves earth in his spaceship and continues his extraterrestrial voyage.

The algorithm presented to the alien consists of a mixture of English and a high-level programming language like C#. Often, programmers (who are sometimes accused of having a thinking process somewhere between that of a man and a machine) use this "language" to express algorithms. It is referred to as pseudocode.

Note

Generally, the steps of the pseudocode are processed one after the other in the order in which they are written.

The next phase after constructing the pseudocode is to convert it into C# source code consisting of instructions to the computer that follow the language rules of C#. This is a relatively easy task, because each step of the pseudocode more or less becomes one C# instruction, and because the instructions are written in the same sequence as their corresponding pseudocode steps.

Note

Generally, the instructions of the C# source code are executed one after the other by the computer, in the order in which they are written.

Most algorithms need to store some intermediate results, such as Sum and ListSize in our alien example. When the algorithm is translated into C#, those intermediate results are referred to as variables and will be stored in the computer's main memory during execution instead of on the paper in the example. I will introduce variables further in Chapter 3, "A Guided Tour Through C#: Part I."

---