6.5 Expressing Algorithms
In the previous sections, we have written programs to write out a greeting, read characters in and write them out in reverse order, add numbers together and print an error message if the sum is negative, and enter a value and read and sum that many numbers. We expressed the solution to each problem in paragraph form and then wrote the code. In computing, the plan for a solution is called an algorithm. As you saw, going from the problem in paragraph form to the code is not always a clear-cut process. Pseudocode is a language that allows us to express algorithms in a clearer form.
Pseudocode Functionality
Pseudocode is not a real computer language, but rather a shorthand-like language that people use to express actions. There are no special grammar rules for pseudocode, but to express actions we must be able to represent the following concepts.
Variables
Names that appear in pseudocode algorithms refer to places in memory where values are stored. The name should reflect the role of the content in the algorithm. For example, the variable sum could be used to represent the summation of a set of other values.
Assignment
If we have variables, we must have a way to put a value into one. We use the statement
Set sum to 0
to store a value into the variable sum. Another way of expressing the same concept uses a back arrow (<—):
sum <— 1
When we want to access the value of the variable later, we just use the name. For example, we access the values in sum and num in the following statement:
Set sum to sum + num
or
sum <— sum + num
The value stored in sum is added to the value in num and the result is stored back in sum. Thus, when a variable is used on the right side of the to or <—, the value of the variable is accessed. When a variable is used following Set or on the left side of <—, a value is stored into the variable.
The value being stored into a variable can be a single value (as in 0) or an expression made up of variables and operators (as in sum + num).
Input/Output
Most computer programs simply process data of some sort, so we must be able to input data values from the outside world and output the result on the screen. We can use the word write for output and the word read for input.
Write “Enter the number of values to read and sum”
Read num
The characters between the double quotation marks are called strings and tell the user what to enter or to describe what is written. It doesn’t matter which exact words you use: Display or Print would be equivalent to Write; Get or Input would be synonyms for Read. Remember, pseudocode algorithms are written for a human to translate into some programming language at a later stage, so there are no set rules. However, being consistent within a project is a good idea—both for you as you are working and for the person following you, who may have to interpret what you have written.
The last two output statements demonstrate an important point:
Write “Err”
Write sum
The first writes the characters between the double quotation marks on the screen. The second writes the contents of the variable sum on the screen. The value in sum is not changed.
Selection
The selection construct allows a choice between performing an action or skipping it. Selection also allows a choice between two actions. The condition in parentheses determines which course of action to follow. For example, the following pseudocode segment prints the sum or an error message.
// Read and sum three numbers
IF (sum < 0)
Print error message
ELSE
Print sum
// Whatever comes next
We use indention to group statements (only one in this case). Control goes back to the statement that is not indented. The // introduces a comment to the reader, which is not part of the algorithm.
This version of the selection construct is called the if-then-else version because the algorithm chooses between two actions. The if-then version is the case where an action is executed or skipped. If we wanted to print the sum in any event, we could show the algorithm this way.
// Read and sum three numbers
IF(sum < 0)
Print error message
Print sum
// Whatever comes next
Repetition
The repetition construct allows instructions to be repeated. In the summing problem, for example, a counter is initialized, tested, and incremented. Pseudocode allows us to outline the algorithm so that the pattern becomes clear. Like the selection construct, the expression in parentheses beside the WHILE is a test. If the test is true, the indented code is executed. If the test is false, execution skips to the next non-indented statement.
Set limit to number of values to sum
WHILE (counter < limit)
Read num
Set sum to sum + num
Set counter to counter + 1
// Rest of program
The expression in parentheses beside the WHILE and the IF is a Boolean expression, which evaluates to either true or false. In the IF, if the expression is true, the indented block is executed. If the expression is false, the indented block is skipped and the block below the ELSE is executed if it exists. In the WHILE, if the expression is true, the indented code is executed. If the expression is false, execution skips to the next non-indented statement. We are putting WHILE, IF, and ELSE in all capital letters because they are often used directly in various programming languages. They have special meanings in computing.
TABLE 6.1 summarizes the pseudocode elements we’ve covered
| TABLE | ||
| 6.1 Pseudocode Elements | ||
| Construct | What It Means | Example |
| Variables | Named places into which values are stored and from which values are retrieved. | sum, total, counter, name |
| Assignment | Storing a value into a variable. | Set number to 1 number <— 1 |
| Input/output | Input: reading in a value, probably from the keyboard. Output: displaying the contents of a variable or a string, probably on the screen. |
Read number Get number Write number Display number Write "Have a good day" |
| Repetition (iteration, looping) | Repeat one or more statements as long as a condition is true. | While (condition) // Execute indented statement(s) |
| Selection: if-then | If a condition is true, execute the indented statements; if a condition is not true, skip the indented statements. | IF (newBase = 10) Write "You are converting " Write "to the same base." // Rest of code |
| Selection: if-then-else | If a condition is true, execute the indented statements; if a condition is not true, execute the indented statements below ELSE. | IF (newBase = 10) Write "You are converting " Write " to the same base." ELSE Write "This base is not the " Write "same." // Rest of code |
Here is the pseudocode algorithm for the program that read and summed two values and printed an error message if the total was negative:
Set sum to 0
Read num1
Set sum to sum + num1
Read num2
Set sum to sum + num2
If (sum < 0)
Write “Error”
ELSE
Write sum
Here is the pseudocode algorithm for the program that input the number of values to read, read them, and printed the sum:
Set counter to 0
Set sum to 0
Read limit
While (counter < limit)
Read num
Set sum to sum + num
Set counter to counter + 1
Print sum
Note that expressing an idea in pseudocode might translate to many instructions in low-level languages like assembly language.
Following a Pseudocode Algorithm
In Chapter 2, we introduced an algorithm for converting from base 10 to other bases. We expressed this algorithm in pseudocode for a human to follow.
While (the quotient is not zero)
Divide the decimal number by the new base
Set the next digit to the left in the answer to the remainder
Set the decimal number to the quotient
To refresh our memories, we apply this algorithm to convert decimal number 93 to octal. We divide 93 by 8 (the new base), giving a quotient of 11 and a remainder of 5. This is the first division, so 5 becomes the digit in the units position of the answer. The original decimal number (93) is replaced by the quotient, 11. The quotient is not 0, so we divide 11 by 8, giving a quotient of 1 and a remainder of 3. The digit 3 becomes the digit to the left of 5, giving a temporary answer of 35. The current decimal number (11) is replaced by the quotient 1. The quotient is not 0, so we divide it by 8, giving a quotient of 0 and a remainder of 1. The digit 1 becomes the leftmost digit in the answer, giving a value of 135. The quotient is 0, so the process ends.
This paragraph again shows how challenging English descriptions can be to read! First let’s summarize the calculations.
Now let’s start over again, giving names to the values that we need to keep: decimalNumber, newBase, quotient, remainder, and answer. We depict these items as named boxes in which we write a value. See FIGURE 6.6(a). We have put a question mark in boxes for which we do not know the contents.
FIGURE 6.6 Walk-through of a conversion algorithm
In following an algorithm, we draw boxes for variables and fill in the values. The algorithm begins by asking if the value in quotient is 0. Let’s assume it is not, but we’ll come back to this point later. FIGURE 6.6(b) shows the results after the first time through the loop, dividing 93 by 8. The quotient is 11, so we repeat the process. FIGURE 6.6(c) displays the values after this repetition. The quotient is not 0, so we divide 1 by 8, giving the situation in FIGURE 6.6(d). Now the quotient is 0, so the process stops.
One of our boxes, decimalNumber, originally contained the initial data value for the problem, the number to be converted. In a computer algorithm, we must give instructions to someone at the keyboard to input this value (this is called a prompt). Box newBase did not change throughout the process, but it too must be input from the keyboard because the algorithm is to change a decimal number into some other base. So the new base— base 8 in this case—must be input to the problem.
When we went through this algorithm, we knew that quotient had not been calculated yet, so we could assume it was not 0. In an algorithm for a computer to follow, we must make sure that the quotient is not 0 by setting it to some nonzero value initially.
Here is the same algorithm rewritten in concrete steps from which a program could be written. DIV is an operator that returns the decimal quotient, and REM is an operator that returns the decimal remainder.
Write “Enter the new base”
Read newBase
Write “Enter the number to be converted”
Read decimalNumber
Set answer to 0
Set quotient to decimal number
While (quotient is not zero)
Set quotient to decimalNumber DIV newBase
Set remainder to decimalNumber REM newBase
Make the remainder the next digit to the left in the answer
Set decimalNumber to quotient
Write “The answer is”, answer
Writing a Pseudocode Algorithm
Here we will walk you through the algorithm development process on a small scale, pointing out strategies that we are using. In Chapter 7, we explore writing algorithms in more depth.
Let’s read in pairs of positive numbers and print each pair in numeric order. If there is more than one pair of numbers, we must have a loop. Here is a first approximation of the algorithm:
While (not done)
Write “Enter two values separated by a blank; press return”
Read number1
Read number2
Print them in order
How do we know when to stop? That is, how do we break down not done into a question? We can ask the user to tell you how many pairs are to be entered. Here is the second pass:
Write “How many pairs of values are to be entered?”
Read numberOfPairs
Set pairsRead to 0
While (pairsRead < numberOfPairs)
Write “Enter two values separated by a blank; press return”
Read number1
Read number2
Print them in order
How do we determine the order of the numbers? We compare the values using the conditional construct. If number1 is less than number2, we print number1 and then number2. Otherwise, we print number2 and then number1. Before we complete the algorithm, have we forgotten anything? numberRead never changes! We must increment numberRead.
Write “How many pairs of values are to be entered?”
Read numberOfPairs
Set numberRead to 0
While (numberRead < numberOfPairs)
Write “Enter two values separated by a blank; press return”
Read number1
Read number2
If (number1 < number2)
Print number1 , “ ” , number2
ELSE
Print number2 , “ ” , number1
Set numberRead to numberRead + 1
In going through the process of writing this algorithm, we used two major strategies. We asked questions and we deferred details. Asking questions is a strategy with which most of us are familiar. Deferring details means giving a task a name and then filling in the details of how to accomplish that task at a later time. That is, we first wrote the algorithm using more pairs and print them in order; then we filled in the details of how to accomplish these tasks at a later time.
An algorithm is not complete until it has been tested. We can use the same technique that we relied on to simulate the base conversion algorithm: We can choose data values and work through the code with paper and pencil. This algorithm has four variables that we must trace: numberOfPairs, numberRead, number1, and number2. Let’s assume the user enters the following data when prompted:
3
10 20
20 10
10 10
FIGURE 6.7(a) shows the values of the variables at the beginning of the loop. numberRead is less than numberOfPairs, so the loop is entered. The prompt is issued and the two numbers are read. number1 is 10 and number2 is 20, so the if statement takes the then branch. number1 is printed, followed by number2. numberRead is incremented. FIGURE 6.7(b) shows the values at the end of the first repetition. numberRead is still less than numberOfPairs, so the code is repeated. The numbers are prompted for and read. number1 is 20 and number2 is 10, so the else branch is taken. number2 is printed, followed by number1. numberRead is incremented, resulting in the state of the variables at the end of the second iteration as shown in FIGURE 6.7(c).
numberRead is less than numberOfPairs, so the code is repeated. The inputs are prompted for and read, making number1 10 and number2 10. Because number1 is not less than number2, the else branch is taken. number2 is printed, followed by number1. Because the values are the same, it doesn’t matter in which order they are printed. numberRead is incremented. numberRead is now not less than numberOfPairs, so the code is not repeated.
FIGURE 6.7 Walk-through of pairs algorithm
In this process, which is called desk checking, we sit at a desk with a pencil and paper and work through the design. It is useful to take actual data values and trace what happens to them as we reason about the design. This technique is simple but amazingly effective.
Translating a Pseudocode Algorithm
In Chapter 1, we described the layers of languages that were produced over time. In this chapter, we began with machine language (the lowest layer) and moved up one step to assembly language. How we translate a pseudocode algorithm depends on the language into which we are translating the algorithm. Here, where we are limited by the limits of an assembly language, one pseudocode statement often requires several Pep/9 statements.
We have written our algorithm as an interactive program. That is, the program asks the user to do something. In this case, the first instruction was to write a request to the user to enter the number of pairs. This is exceptionally easy in a high-level language, but more complicated in Pep/9. First we have to set up the message using a .ASCII pseudo-operation and then set up the code to have it written out. Let’s shorten the message to “Enter number.” STRO is used to print the message.
mesgl: |
.ASCII |
"Enter numberx00" |
; First message |
. . . |
STRO |
mesgl |
; Write message |
Reading the number of pairs can be done with one Pep/9 instruction. Setting the number read to 0 can be done in one pseudo-operation. We set up the loop by loading the number read into the A register (the accumulator) and comparing it with the number to be read. Once within the loop, a second instruction is given to the user. Let’s put these pieces together.
|
BR |
main |
|
mesgl: |
.ASCII |
"Enter numberx00" |
; |
mesg2: |
.ASCII |
"Enter pairsx00" |
; |
numRead: |
.WORD |
0x00 |
; |
numPairs: |
.BLOCK |
2 |
; |
numberl: |
.BLOCK |
2 |
; |
number2: |
.BLOCK |
2 |
; |
main: |
STRO |
mesg1,d |
; |
DECI |
numPairs,d |
; |
|
begin: |
... |
mesg2,d |
; |
|
BR |
begin |
; |
Now we must translate the loop body, which requires writing a message, reading two values, and comparing them. The first two tasks require only one Pep/9 statement each, but the if-then-else statement will take more work. To complete the program, you would write the code to print each of the two statements, give names to the first instruction in each code block, and then determine which block should be executed. We leave these last steps as an exercise.